1. Turing machines 15

where n is the length of the input. If F is a predicate, we say that it is

decidable in polynomial time.

The class of all functions computable in polynomial time, or all predicates

decidable in polynomial time (sometimes we call them “polynomial predi-

cates” for brevity), is denoted by P. (Some other complexity classes consid-

ered below are only defined for predicates.) Note that if F is computable

in polynomial time, then |F(x)| = poly(|x|), since the output length cannot

exceed the maximum of the input length and the number of computation

steps. (Here |t| stands for the length of the string t.)

The computability in polynomial time is still a theoretic notion: if the

degree of the polynomial is large (or the constant c is large), an algorithm

running in polynomial time may be quite impractical.

One may use other computational models instead of Turing machines to

define the class P. For example, we may use a usual programming language

dealing with integer variables, if we require that all integers used in the

program have at most poly(n) bits.

In speaking about polynomial time computation, one should be careful

about encoding. For example, it is easy to see that the predicate that is true

for all unary representations of prime numbers (i.e., strings 1 . . . 1 whose

length N is a prime number) is polynomial. Indeed, the obvious algorithm

that tries to divide N by all numbers ≤

√

N runs in polynomial time, namely,

poly(N). On the other hand, we do not know whether the predicate P (x) =

“x is a binary representation of a prime number” is polynomial or not. For

this to be true, there should exist an algorithm with running time poly(n),

where n = log2 N is the length of the binary string x. (A probabilistic

polynomial algorithm for this problem is known; see below.)

Definition 1.5. A function (predicate) F on

B∗

is computable (decidable)

in polynomial space if there exists a Turing machine that computes F and

runs in space s(n) = poly(n), where n is the length of the input.

The class of all functions (predicates) computable (decidable) in polynomial

space is called PSPACE.

Note that any machine that runs in polynomial time also runs in polyno-

mial space, therefore P ⊆ PSPACE. Most experts believe that this inclusion

is strict, i.e., P = PSPACE, although nobody has succeeded in proving it so

far. This is a famous open problem.

Problems

[1] 1.1. Construct a Turing machine that reverses its input (e.g., produces

“0010111” from “1110100”).