PSPACE-CompletenessPSPACE-completeness definedThe TQBF problemThe PSPACE-completeness of TQBF – proof ideaA polynomial space algorithm for TQBFFormulas as gamesThe FORMULA-GAME problemThe child’s game GeographyGeneralized GeographySlide 10Slide 11Slide 12Slide 13Slide 14GG and its PSPACE-completenessWhy GGPSPACEWhy GG is PSPACE-hard (a)Why GG is PSPACE-hard (b)Why GG is PSPACE-hard (c)Why GG is PSPACE-hard (d)PSPACE-CompletenessPSPACE-CompletenessSection 8.3 Giorgi Japaridze Theory of ComputabilityPSPACE-completeness defined 8.3.aGiorgi Japaridze Theory of ComputabilityDefinition 8.8 A language B is PSPACE-complete iff it satisfies twoconditions: 1. B is in PSPACE, and 2. every A in PSPACE is polynomial time reducible to B.If B merely satisfies condition 2, we say that it is PSPACE-hard.Why do we still appeal to polynomial time reducibility and not, say, polynomial space reducibility, philosophically speaking? A reduction must be easy relative to the class (of difficult problems) that we are defining. Only then it is the case that if we find an easyway to solve a (PSPACE-, NP- or whatever-) complete problem, easy solutions to other (reducible to it) problems would also be found. If the reduction itself is hard, it does not at all offer an easy way to solve problems.The TQBF problem 8.3.bGiorgi Japaridze Theory of ComputabilityUniversal quantifier : xP(x) means “for any x{0,1}, P(x) is true”Existential quantifier : xP(x) means “for some x{0,1}, P(x) is true”We consider fully quantified Boolean formulas (in the prenex form).These are Boolean formulas prefixed with either x or x for each variable x. Examples (true or false?):x(xx)x(xx)x(xx)xy(xy)xy ((xy)(xy))xy (xy)xy ((xy)(xy))zxy ((xyz)(xyz))TQBF = {<> |  is a true fully quantified Boolean formula} (True Quantified Boolean Formulas)The PSPACE-completeness of TQBF – proof idea 8.3.cGiorgi Japaridze Theory of ComputabilityTheorem 8.9 TQBF is PSPACE-complete.Proof idea. To show that TQBFPSPACE, we give an algorithm that assigns values tothe variables and recursively evaluates the truth of the formula for those values. To show that ApTQBF for every APSPACE, we begin with a polynomial-space machine M for A. Then we give a polynomial time reduction that maps a string w to a formula  that encodes a simulation of M on input w.  is true iff M accepts w (andhence iff wA). A first, naive, attempt to do so could be trying to precisely imitate the proof of the Cook-Levin theorem. We can indeed construct a  that simulates M on input w by expressing the requirements for an accepting tableau. As in the proof of the Cook-Levintheorem, such a tableau has polynomial width O(nk), the space used by M. But the problem is that the height of the tableau would be exponential! Instead, we use a technique related to the proof of Savitch’s theorem to construct theformula. The formula divides the tableau into halves and employs the universal quantifier to represent each half with the same part of the formula. The result is a muchshorter formula. End of proof ideaA polynomial space algorithm for TQBF 8.3.dGiorgi Japaridze Theory of ComputabilityThe following algorithm obviously decides TQBF:T = “On input <>, a fully quantified Boolean formula: 1. If  contains no quantifiers, then it is an expression with only constants, so evaluate  and accept if true, otherwise, reject. 2. If  is x, recursively call T on , first with 0 substituted for x and then 1 substituted for x. If either result is accept, then accept; otherwise, reject. 3. If  is x, recursively call T on , first with 0 substituted for x and then 1 substituted for x. If both results are accept, then accept; otherwise, reject.”Analysis: Let m be the number of variables that appear in . The depth of recursion does not exceed m. And at each level of recursion, we need only store the value of one variable. So, the total space used is O(m), and hence linear in the size of . To complete the proof of Theorem 8.9, we also need to show that TQBF is PSPACE- hard. A a detailed technical proof of this part is technically somewhat trickier than (butotherwise similar to) the proof of the Cook-Levin theorem, and we omit it.Formulas as games 8.3.eGiorgi Japaridze Theory of ComputabilityEach fully quantified Boolean formula (in prenex form)  can be seen as a game between two players A and E. If  =x(x), it is A’s move, who should select x=0 or x=1, after which the game continues as (0) or (1), respectively.xyz[(xy)(yz)(yz)] E moves, selects x=1 yz[(1y)(yz)(yz)] A moves, selects y=0 z[(10)(0z)(0z)] E moves, selects z=1 (10)(01)(01) A wins If  =x(x), it is E’s move, who should select x=0 or x=1, after which the game continues as (0) or (1), respectively. The play continues until all quantifiers are stripped off, after which E is considered the winner iff the final, variable-free formula, is true. Who has a winning strategy (a strategy that guarantees a win no matterhow the adversary acts) in this example?--- Player A has a winning strategy: No matter what E does, select y=0.The FORMULA-GAME problem 8.3.fGiorgi Japaridze Theory of Computabilityxyz[(xy)(yz)(yz)] ?E: Select x=1, and select z to be the negation of whatever A selects for y. Who has a winning strategy inFORMULA-GAME = {<> | Player E has a winning strategy in }Theorem 8.11 FORMULA-GAME is PSPACE-complete.Proof . This is so for a simple reason: we simply have FORMULA-GAME = TQBF.To see this, observe that  is true iff player E has a winning strategy in it. A detailed proof of this fact (if it was necessary) can proceed by induction on the length of the quantifier-prefix of .The child’s game Geography 8.3.gGiorgi Japaridze Theory of Computability Players, called I and II, take turns naming cities from anywhere in the world (playerI starts). Each city chosen must begin with the same letter that ended the previous city’s name. Repetitions are not permitted. The player who is unable to continue loses. We can model this game