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
Previous Page Next Page