Problem Solving in Automata, Languages, and Complexity

6

Computational

Complexity

6.1 Asymptotic Growth Rate

In the last two chapters, we have established a computability theory and,
based on the Church-Turing Thesis, identified recursive functions as the class
of computable functions. In this chapter, we extend this theory to a com-
putational complexity theory, in which we study the computation time and
space required to compute a recursive function by Turing machines. One of
the goals of this computational complexity theory is to identify the class of
feasibly solvable problems, that is, the class of functions that can be computed
by a Turing machine within a reasonable amount of time and using a reason-
able amount of memory space. To understand what “reasonable” means, we
first look at a simple example.

Example 6.1 Suppose we are given three pegs and n disks, with all n disks

having different size. Initially, the n disks are stacked in decreasing size, from

bottom to top, in the first peg (see Figure 6. I). The TOWER OF HANOI problem

is to transfer the entire tower of n disks from the first peg to the second peg,

moving one disk at a time and never putting a larger disk on top of a smaller

disk. What is the fastest solution to this problem? Is the fastest solution

feasible for size n = 64 (the size of the original Tower of Hanoi problem)?

Solution. Suppose n = 1. Then, it is obvious that one move is all it takes.
Now, suppose n > 1. Then, we can solve this problem recursively: We first
move the top n - 1 disks to the third peg. Next, we move the bottom disk
(the largest disk) to th e second peg. After that, we move the other n - 1 disks
281

Problem Solving in Automata, Languages, and Complexity.

Ding-Zhu Du, Ker-I Ko

Copyright2001 by John Wiley & Sons, Inc.

ISBNs: 0-471-43960-6 (Hardback); 0-471-22464-2 (Electronic)