6. What Can and Cannot Be Proven about Computational Complexity
Society for Industrial and Applied Mathematics eBooks · 1989
In this section we consider the problem of what can and cannot be formally proven about complexity of computations and complexity classes. This work is motivated by the current interest in computer science in proving properties of programs and by the general desire to understand better what can and cannot be proven formally about the complexity of computations. As we will see in this chapter, the results about complexity of computations change quite radically if we consider only properties of computations which can be proven formally. As a matter of fact, these results suggest that we must adjust our intuitive ideas about computational complexity in view of these results and, we believe, that this problem area deserves a thorough investigation [17], [20], [44]. We first look at the problem of proving sharp time bounds for the running times of one-tape (k-tape) Turing machines and relate this problem to a fundamental problem about what can and cannot be formally proven about computational complexity classes [20]. An important problem in computational complexity theory is to determine, for a given computer model and computer resource, how much a given resource bound T(n) (satisfying some honesty conditions) has to be increased to be able to compute something new which cannot be computed in the old resource bound T(n). The standard way to obtain separation results for complexity classes is by efficiently diagonalizing over all the computations which can be performed in the given resource bound. The efficiency of the diagonal process over the resource bounded computations, or the additional amount of resources required to carry out the diagonalization over all the computations computable within the given resource bound, determines the sharpness of the results. The usual way to carry out such diagonal processes is to bound the given resource as a function of the length of the input and by simulation determine on successive inputs what different Turing machines do and do the opposite, provided their simulation did not try to exceed the given resource bound [18], [20], [27]. Such diagonal processes, in essence, require that we perform two separate computations: a simulation process and a process which shuts the computation off if it tries to use too much of the bounded resource. This method works very well for reusable resource measures where we can first compute the resource bound and then perform the simulation within the bounded resources. For example, for the tape bounded Turing machine computations the following result holds [22], [27].