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.