3. The class NP: Reducibility and completeness 27

the machine either stops within exp(O(s)) steps, or enters a cycle and runs

forever.

[2!] 2.17 (“Small depth circuits can be simulated in small space”). Prove

that there exists a Turing machine that evaluates the output variables of a

circuit of depth d over a fixed basis, using work space O(d + log m) (where

m is the number of the output variables). The input to the machine consists

of a description of the circuit and the values of its input variables.

[3!] 2.18 (“Computation with small space is parallelizable”). Let M be a

Turing machine. For each choice of n, m, s, let fn,m,s :

Bn

→

Bm

be the

function computed by the machine M with space s (it may be a partial

function). Prove that there exists a family of exp(O(s))-size,

O(s2)-depth

circuits Cn,m,s which compute the functions fn,m,s.

(These circuits can be constructed by a TM with space O(s), but we

will not prove that.)

The reader might wonder why we discuss the space restriction in terms

of Turing machines while the circuit language is apparently more convenient.

So, let us ask this question: what is the circuit analog of the computation

space? The obvious answer is that it is the circuit width.

Let C be a circuit whose gates are arranged into d layers. The width

of C is the maximum amount of information carried between the layers,

not including the input variables. More formally, for each l = 1,...,d we

define wl to be the number of auxiliary variables from layers 1,...,l that

are output variables or connected to some variables from layers l+1,...,d

(i.e., used in the right-hand side of the corresponding assignments). Then

the width of C is w = max{w1,...,wd}.

But here comes a little surprise: any Boolean function can be computed

by a circuit of bounded width (see Problem 2.19 below). Therefore the width

is rather meaningless parameter, unless we put some other restrictions on

the circuit. To characterize computation with limited space (e.g., the class

PSPACE), one has to use either Turing machines, or some class of circuits

with regular structure.

[3] 2.19 (Barrington [8]). Let C be a formula of depth d that computes a

Boolean function f(x1,...,xn). Construct a circuit of size exp(O(d)) and

width O(1) that computes the same function.

3. The class NP: Reducibility and completeness

3.1. Nondeterministic Turing machines. NP is the class of predicates

recognizable in polynomial time by “nondeterministic Turing machines.”

(The word “nondeterministic” is not appropriate but widely used.)