CSC 341: May 11, 2007
From CSWiki
[edit]
Notes for the class session
I don't have many notes at all for this class session. Someone who took better notes might be able to help.
Generalized hex: φ is true if, and only if, player 1 has a winning strategy in <G, s, t>.
[edit]
Study question
- Suppose that we introduce a third Boolean quantifier, in addition to the universal (
) and existential (
) used in TQBF formulas: The 
quantifier, meaning that the formula in its scope is true for one value of the variable and false for the other. Let MTQBF be the set of true totally quantified Boolean formulas that may use this quantifier. Show that MTQBF is PSPACE-complete.
[edit]
Proposed Solutions
- In order for MTQBF to be PSPACE-complete, MTQBF must be in PSPACE and another PSPACE-complete language must be polynomial time reducible to it. An algorithm to decide MTQBF in PSPACE follows the same three steps as the algorithm T in theorem 8.9. After the last step, this fourth step is added:
4. If φ equals 
ψ, recursively call T on ψ, first with 0 substituted for f and then with 1 substituted for f. If one result is accept and the other is reject, then accept; otherwise reject.
MTQBF is PSPACE-complete because 
. This is easy to show, because any input on the language TQBF can be run on the extended version of T used for MTQBF. The new step will just be skipped because no member of TQBF will contain a .
