5. The hierarchy of complexity classes 51
formula
w1
1
w1
2
. . .
w1(|x|) p
b1
1
. . .
bp(|x|)
1
w2
1
. . .
w2(|x|) p
. . . S(x, w1,w1,...
1 2
),
where S (·) denotes the Boolean function computed by the circuit. (Boolean
variables
w1,...,w1(|x|)
1
p
encode the first move of W, variables
b1,...,bp(|x|)11
encode B’s answer,
w2,...,w2(|x|)
1
p
encode the second move of W, etc.)
In order to convert S into a Boolean formula, recall that a circuit is
a sequence of assignments yi := Ri that determine the values of auxiliary
Boolean variables yi. Then we can replace S (·) by a formula
∃y1,..., ∃ys
(
(y1 R1) · · · (ys Rs) ys
)
,
where s is the size of the circuit.
After this substitution we obtain a quantified Boolean formula which is
true if and only if x L.
Remark 5.1. Note the similarity between Theorem 5.3 (which is about
polynomial space computation) and Problems 2.17 and 2.18 (which are
basically about poly-logarithmic space computation). Also note that a
polynomial-size quantified Boolean formula may be regarded as a polyno-
mial depth circuit (though of very special structure): the and quantifiers
are similar to the and gates. It is not surprising that the solutions are
based on much the same ideas. In particular, the reduction from NTM to
TQBF is similar to the parallel simulation of a finite-state automaton (see
Problem 2.11). However, in the case of TQBF we could afford reasoning at
a more abstract level: with greater amount of computational resources we
were sure that all bookkeeping constructions could be implemented. This
is one of the reasons why “big” computational classes (like PSPACE) are
popular among computer scientists, in spite of being apparently impractical.
In fact, it is sometimes easier to prove something about big classes, and then
scale down the problem parameters while fixing some details.
Previous Page Next Page