Free Trial

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

Polynomial-Time Computability 149 Next, we want to define EXPTIME and EXPSPACE. A language L belongs to EXPTIME if there is a program and a polynomial p such that the program computes the characteristic function of L at each word x in at most 2 p(|x|) steps. And a language L belongs to EXPSPACE 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 2 p(|x|) . We claim that PSPACE EXPTIME. Suppose a computation uses space p(|x|). Then for some constants, c and k, that depend on the program (but not on x), the running time is bounded by c2 kp(|x|) = 2 ln c+kp(|x|) . We observe that the exponent here is a polynomial in |x|. Moreover, EXPTIME EXPSPACE. Suppose a computation uses time 2 p(|x|) . Then the space is bounded by |x| + 2 p(|x|) . This is in turn bounded by 2 q(|x|) for a suitable polynomial q; see Exercise 4. Thus, we are left with the inclusions P PSPACE EXPTIME EXPSPACE PR, where PR is the class of primitive recursive languages. There are numerous questions that can be raised regarding these classes. For some of the questions, answers are known, whereas other questions remain open. The subject of computational complexity is young and growing. See the list of references for some avenues well worth exploring.