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
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.
 1.1. Construct a Turing machine that reverses its input (e.g., produces
“0010111” from “1110100”).