3. The class NP: Reducibility and completeness 27
the machine either stops within exp(O(s)) steps, or enters a cycle and runs
[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 :

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,
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.)
Previous Page Next Page