50 1. Classical Computation

Ó

Ó

¦¾ ¥¾

¦¾ ¥¾

¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡

Fig. 5.1. Inclusion diagram for computational classes. An arrow from

A to B means that B is a subset of A.

prove this by a rather simple “diagonalization argument” (cf. solution to

Problem 1.3).

[3!] Problem 5.2. A Turing machine with oracle for language L uses a

decision procedure for L as an external subroutine (cf. Definition 2.2). The

machine has a supplementary oracle tape, where it can write strings and

then ask the “oracle” whether the string written on the oracle tape belongs

to L.

Prove that any language that is decidable in polynomial time by a TM

with oracle for some L ∈ Σk (or L ∈ Πk) belongs to Σk+1 ∩ Πk+1.

The class PSPACE has complete problems (to which any problem from

PSPACE is reducible). Here is one of them.

The TQBF Problem is given by the predicate

TQBF (x) ⇔ x is a True Quantified Boolean Formula, i.e., a true state-

ment of type Q1y1 . . . QnynF(y1,...,yn), where variables

yi range over B = {0, 1}, F is some propositional formula

(involving y1,...,yn, ¬, ∧, ∨), and Qi is either ∀ or ∃.

By definition, ∀y A(y) means (A(0) ∧ A(1)) and ∃y A(y) means (A(0) ∨

A(1)).

Theorem 5.3. TQBF is PSPACE-complete.

Proof. We reduce an arbitrary language L ∈ PSPACE to TQBF . Using

Theorem 5.2, we construct a game that corresponds to L. Then we convert

a TM that computes the result of the game (a predicate W ) into a circuit.

Moves of the players are encoded by Boolean variables. Then the existence

of the winning strategy for W can be represented by a quantified Boolean