From Theorem 11.5 we use the idea of recursive doubling to express the idea that one ID can become another in some large number of moves. That is, to say that ID / can become ID J in m moves, we say that there exists some ID К such that I becomes К in m/2 moves and К becomes J in another m/2 moves. The language of quantified boolean formulas lets us say these things in a polynomial-length expression, even if m is exponential in the length of the input.

Before proceeding to the proof that every language in PS is polynomial-time reducible to QBF, we need to show that QBF is in PS. Even this part of the PS-completeness proof requires some thought, so we isolate it as a separate theorem.

Theorem 11.10: QBF is in PS.

PROOF: We discussed in Section 11.3.3 the recursive process for evaluating a QBF F. We can implement this algorithm using a stack, which we may store on the tape of a Turing machine, as we did in the proof of Theorem 11.5. Suppose F is of length n. Then we create a record of length 0{n) for F that includes F itself and space for a notation about which subexpression of F we are working on. Two examples among the six possible forms of F will make the evaluation process clear.

1. Suppose F = Fi + F2. Then we do the following:

(a) Place Fi in its own record to the right of the record for F.

(b) Recursively evaluate Fi.

(c) If the value of Fi is 1, return the value 1 for F.

(d) But if the value of Fy is 0, replace its record by a record for F2 and recursively evaluate F.

(e) Return as the value of F whatever value F2 returns.

2. Suppose F = {3x){E). Then do the following:

(a) Create the expression Eo by substituting 0 for each occurrence of x, and place Eq in a record of its own, to the right of the record for F.

(b) Recursively evaluate Eq.

(c) If the value of Eo is 1, then return 1 as the value of F.

(d) But if the value of Eq is 0, create Ey by substituting 1 for x in Е.

(e) Replace the record for Eb by a record for Ey , and recursively evaluate

(f) Return as the value of F whatever value Ei returns.

We shall leave to you the similar steps that will evaluate F for the cases that F is of the other four possible forms: FyFi, - E, (E), or {Ух){Е). The basis

case, were F is a constant, requires us to return that constant, and no ftirther records are created on the tape.

In any case, we note that to the right of the record for an expression of length m will be a record for an expression of length less than m. Note that even though we often have to evaluate two different subexpressions, we do so one-at-a-tinie. Thus, in case (1) above, there are never records for both Fl or any of its subexpressions and F3 or its subexpressions on the tape at the same time. The same is true of Eq and Fi in case (2) above.

Therefore, if wc start with an expression of length n, there can never be more than n records on the stack. Also, each record is 0(n) in length. Thus, the entire tape never grows longer than 0{л?). We now have a construction for a polynomial-spact-bounded TM that accepts QBF; its space bound is quadratic. Note that this algorithm will typically take time that is exponential in n, so it is not polynomial-time bounded. □

Now, we turn to the reduction from an arbitrary language L in PS to the problem QBF. We would like to use prepositional variables yijA as we did in Theorem 10,9 to assert that the jth position in the ith ID is A. However, since there are exponentially many IDs, we could not take an input w of length n and even write down these variables in time that is polynomial in n. Instead, we exploit the availability of quantihers to make the same set of variables represent many different IDs. The idea appears in the proof below.

Theorem 11.11: The problem QBF is PS-complete.

PROOF: Let L be in PS, accepted by a deterministic TM M that uses p(n] space at most, on input of length n. By Theorem 11.3, we know there is a constant с such that M accepts within c-f ) moves if it accepts an input of length n. We shall describe how, in polynomial time, we take an input w of length n and construct from w a QBF E that has no free variables, and has the value 1 if and only if w is in L(M),

In writing E, we shall have need to introduce polynomially many variable IDs, which are sets of variables pjA that assert the jth position of the represented ID has symbol A. We allow j to range from 0 to p{n). Symbol A is either a tape symbol or state of M. Thus, the number of propositional variables in a variable ID is polynomial in n. We assume that all the propositional variables in different variable IDs are distinct; that is, no propositional variable belongs to two different variable IDs. As long as there is only a polynomial number of variable IDs, the total number of propositional variables is polynomial.

It is convenient to introduce a notation (37), where / is a variable ID. This quantifier stands for (3xi){3x2) (Зх), where Xj,X2, -,.,are all the propositional variables in the variable ID I. Likewise, (V/) stands for the V quantifier applied to all the propositional variables in /,

The QBF we construct for m has the form:

{3h){3Ij){SAN hF)

where:

1. lo and are variable IDs representing the initial and accepting IDs, respectively.

2. S is an expression that says starts right ; i.e., Iq is truly the initial ID of M with input w.

3. is an expression that says moves right ; i.e., M takes Iq to If.

4. F is an expression that says finishes right ; i.e., If is an accepting ID.

Note that, while the entire expression has no fi-ee variables, the variables of Iq wUl appear as free variables in 5, the variables of appear free in F, and both groups of variables appear free in N.

Starts Right

S is the logical AND of literals; each literal is one of the variables oi lo- S has literal yjA if the jth position of the initial ID with input w is Л, and has literal yJJ if not. That is, if w в] аг a , then j/o o > iii > Уа . Упа , and all j/js, for J = n -I- l,n + 2,.., ,p(n) appear without negation, and all other variables of Lo are negated. Here, go is assumed to be the initial state of M, and В is its blcuik.

Finishes Right

In order for /; to be an accepting ID, it must have an accepting state. Therefore, we write F as the logical OR of those variables yjA, chosen from the propositional variables of , for which A is an accepting state. Position j is arbitrary.

Next Move Is Right

The expression N is constructed recursively in a way that lets us double the number of moves considered by adding only 0(p(n)) symbols to the expression beuig constructed, and (more importantly) by spending only 0(р{тг)) time writuig the expression. It is useful to have the shorthand / = J, where / and .1 are variable IDs, to stand for the logical AND of expressions that equate each of the corresponding variables of / and J. That is, if / consists of variables yjA and J consists of variables Zja , then / = J is the AND of expressions {yjAZjA + {yjA){zjA)), where j ranges from 0 to p(n), and A is any tape symbol or state of M.

We now construct expressions Ni{I,J), for г - 1,2,4,8, to mean that /I- J by г or fewer moves. In these expressions, only the propositional variables of variable IDs / and J are free; all other propositional variables are bound.