Computability Theory

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 ...