Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

7.3 Some Other Complexity Classes > 7.3 Some Other Complexity Classes - Pg. 148

148 Computability Theory In a 1975 article, Theodore Baker, John Gill, and Robert Solovay showed that there are oracles B and C such that on the one hand P B = NP B and on the other hand P C = NP C . This result suggests that the "P versus NP" question is difficult because whatever argument might settle the question cannot relativize in a straightforward way. It has also been shown that if we choose the oracle B at random (with respect to the natural probability measure on PN ), then P B = NP B with probability 1. The P versus NP question remains the outstanding problem in theoretical com- puter science. In recognition of this fact, the Clay Mathematics Institute has offered a million-dollar prize for its solution. 7.3 Some Other Complexity Classes And what might lie beyond NP? Although there is some analogy between NP and 1 , what might be analogous to n ? And what might be computable in "exponential time," where we allow the computing time to be bounded by 2 p(|x|) for a polynomial p? As indicated earlier, two reasonable measurements of complexity are time (the number of steps the computation executes before halting) and space (where we take the largest number of symbols a register ever contains in the course of the computa- tion, and add these numbers up for all the registers). These two measurements are related. If a computation halts in time t on input x, then the space used is bounded by t + |x| because writing a symbol takes a step. What about the other direction? Suppose that a particular calculation from a program halts, having used space s. We want a bound on the time it used. Consider the snapshots [location counter, memory number] that arise in the course of the computation. One thing we can be sure of is that no snapshot occurs twice. This is because if a computation ever hits a snapshot for a sec- ond time, then the computation will run forever, returning to this snapshot infinitely often. So for a calculation that halts, the time is bounded by the number of possi- ble snapshots. And what is the number of possible snapshots? For a program with G odel number e, there are at most 1 + lh e values for the location counter. And if ¨ the program addresses k different registers, there could be (for the alphabet {0, 1}) at most 2 ks different values for the memory number. Putting the pieces together, we see that for constants c and k (depending on the program), the running time is bounded by c2 ks . We have been looking at the complexity class P. This class might just as well be called PTIME because it uses time as the complexity measure. A language L (that is, a subset of {0, 1} ) is in the class if its characteristic function at x is computable in time bounded by a polynomial q(|x|) in |x|. Analogously, define PSPACE as follows: A language L belongs to PSPACE if there is a program and a polynomial p such that the program computes the characteristic function of L at each word x using space at most p(|x|). Then P PSPACE because a computation that uses time q(|x|) can use at most space |x| + q(|x|).