Question? Leave a message!




Quantified satisfiability is in PSPACE

Quantified satisfiability is in PSPACE
9. PSPACE PSPACE complexity class ‣ quantified satisfiability ‣ planning problem ‣ PSPACEcomplete ‣ Lecture slides by Kevin Wayne Copyright © 2005 PearsonAddison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinbergtardos Last updated on Sep 8, 2013 6:54 AMGeography game Geography. Alice names capital city c of country she is in. Bob names a capital city c' that starts with the letter on which c ends. Alice and Bob repeat this game until one player is unable to continue. Does Alice have a forced win Ex. Budapest → Tokyo → Ottawa → Ankara → Amsterdam → Moscow → Washington → Nairobi → … Geography on graphs. Given a directed graph G = (V, E) and a start node s, two players alternate turns by following, if possible, an edge out of the current node to an unvisited node. Can first player guarantee to make the last legal move Remark. Some problems (especially involving 2player games and AI) defy classification according to NP, EXPTIME, NP, and NPComplete. 29. PSPACE PSPACE complexity class ‣ quantified satisfiability ‣ planning problem ‣ PSPACEcomplete ‣ SECTION 9.1PSPACE P. Decision problems solvable in polynomial time. PSPACE. Decision problems solvable in polynomial space. Observation. P ⊆ PSPACE. polytime algorithm can consume only polynomial space 4PSPACE n Binary counter. Count from 0 to 2 – 1 in binary. Algorithm. Use n bit odometer. Claim. 3SAT ∈ PSPACE. Pf. n Enumerate all 2 possible truth assignments using counter. Check each assignment to see if it satisfies all clauses. ▪ Theorem. NP ⊆ PSPACE. Pf. Consider arbitrary problem Y ∈ NP. Since Y ≤ 3SAT, there exists algorithm that solves Y in polytime plus P polynomial number of calls to 3SAT black box. Can implement black box in polyspace. ▪ 59. PSPACE PSPACE complexity class ‣ quantified satisfiability ‣ planning problem ‣ PSPACEcomplete ‣ SECTION 9.3Quantified satisfiability QSAT. Let Φ(x , …, x ) be a boolean CNF formula. Is the following 1 n propositional formula true ∃ x ∀ x ∃ x ∀ x … ∀ x ∃ x Φ(x , …, x ) 1 2 3 4 n1 n 1 n assume n is odd Intuition. Amy picks truth value for x , then Bob for x , then Amy for x , 1 2 3 and so on. Can Amy satisfy Φ no matter what Bob does € Ex. (x ∨ x ) ∧ (x ∨ x ) ∧ (x ∨ x ∨ x ) 1 2 2 3 1 2 3 Yes. Amy sets x true; Bob sets x ; Amy sets x to be same as x . 1 2 3 2 (x ∨ x ) ∧ (x ∨ x ) ∧ (x ∨ x ∨ x ) Ex. 1 2 2 3 1 2 3 € No. If Amy sets x false; Bob sets x false; Amy loses; 1 2 No. if Amy sets x true; Bob sets x true; Amy loses. 1 2 € 7Quantified satisfiability is in PSPACE Theorem. QSAT ∈ PSPACE. Pf. Recursively try all possibilities. Only need one bit of information from each subproblem. Amount of space is proportional to depth of function call stack. ∃ return true iff both x = 0 x = 1 1 1 subproblems are true ∀ ∀ return true iff either x = 1 x = 0 2 subproblem is true 2 ∃ ∃ ∃ ∃ x = 0 x = 1 3 3 Φ(0, 0, 0) Φ(0, 0, 1) Φ(0, 1, 0) Φ(0, 1, 1) Φ(1, 0, 0) Φ(1, 0, 1) Φ(1, 1, 0) Φ(1, 1, 1) 89. PSPACE PSPACE complexity class ‣ quantified satisfiability ‣ planning problem ‣ PSPACEcomplete ‣ SECTION 9.415puzzle 8puzzle, 15puzzle. Noyes Chapman 1874 Board: 3by3 grid of tiles labeled 1–8. Legal move: slide neighboring tile into blank (white) square. Find sequence of legal moves to transform initial configuration into goal configuration. 1 2 3 1 2 3 1 2 3 move 6 . . . 4 5 6 4 5 4 5 6 8 7 8 7 6 7 8 goal configuration initial configuration 10Planning problem Conditions. Set C = C , …, C . 1 n Initial configuration. Subset c ⊆ C of conditions initially satisfied. 0 Goal configuration. Subset c ⊆ C of conditions we seek to satisfy. Operators. Set O = O , …, O . 1 k To invoke operator O , must satisfy certain prereq conditions. i After invoking O certain conditions become true, and certain conditions i become false. PLANNING. Is it possible to apply sequence of operators to get from initial configuration to goal configuration Examples. 15puzzle. Rubik's cube. Logistical operations to move people, equipment, and materials. 11Planning problem: 8puzzle Planning example. Can we solve the 8puzzle C means tile i is in square j ij Conditions. C , 1 ≤ i, j ≤ 9. 1 2 3 ij 4 5 6 Initial state. c = C , C , …, C , C , C , C . 0 11 22 66 78 87 99 8 7 9 Goal state. c = C , C , …, C , C , C , C . 11 22 66 77 88 99 O i Operators. 1 2 3 Precondition to apply O = C , C , …, C , C , C , C . i 11 22 66 78 87 99 4 5 6 After invoking O , conditions C and C become true. i 79 97 8 9 7 After invoking O , conditions C and C become false. i 78 99 Solution. No solution to 8puzzle or 15puzzle 12Diversion: Why is 8puzzle unsolvable 8puzzle invariant. Any legal move preserves the parity of the number of pairs of pieces in reverse order (inversions). 3 1 2 3 1 2 3 1 2 4 5 6 4 5 6 4 6 8 7 8 7 8 5 7 3 inversions 3 inversions 5 inversions 13, 23, 78 13, 23, 78 13, 23, 78, 58, 56 1 2 3 1 2 3 4 5 6 4 5 6 7 8 8 7 0 inversions 1 inversion: 78 13Planning problem: binary counter Planning example. Can we increment an nbit counter from the allzeroes state to the allones state C corresponds to bit i = 1 i Conditions. C , …, C . 1 n all 0s Initial state. c = φ. 0 all 1s Goal state. c = C , …, C . 1 n Operators. O , …, O . 1 n i1 least significant bits are 1 To invoke operator O , must satisfy C , …, C . i 1 i–1 set bit i to 1 After invoking O , condition C becomes true. i i set i1 least After invoking O , conditions C , …, C become false. i 1 i–1 significant bits to 0 Solution. ⇒ C ⇒ C ⇒ C , C ⇒ C ⇒ C , C ⇒ … 1 2 1 2 3 3 1 n Observation. Any solution requires at least 2 – 1 steps. 14Planning problem is in EXPTIME Configuration graph G. n Include node for each of 2 possible configurations. Include an edge from configuration c' to configuration c'' if one of the operators can convert from c' to c''. PLANNING. Is there a path from c to c in configuration graph 0 Claim. PLANNING ∈ EXPTIME. Pf. Run BFS to find path from c to c in configuration graph. ▪ 0 n Note. Configuration graph can have 2 nodes, and shortest path can n be of length = 2 – 1. binary counter 15Planning problem is in PSPACE Theorem. PLANNING is in PSPACE. Pf. Suppose there is a path from c to c of length L. 1 2 Path from c to midpoint and from c to midpoint are each ≤ L / 2. 1 2 Enumerate all possible midpoints. Apply recursively. Depth of recursion = log L. ▪ 2 boolean hasPath(c , c , L) 1 2 if (L ≤ 1) return correct answer enumerate using binary counter foreach configuration c' boolean x = hasPath(c , c', L/2) 1 boolean y = hasPath(c , c', L/2) 2 if (x and y) return true return false 169. PSPACE PSPACE complexity class ‣ quantified satisfiability ‣ planning problem ‣ PSPACEcomplete ‣ SECTION 9.5PSPACEcomplete PSPACE. Decision problems solvable in polynomial space. PSPACEComplete. Problem Y ∈ PSPACEcomplete if (i) Y ∈ PSPACE and (ii) for every problem X ∈ PSPACE, X ≤ Y. P Theorem. StockmeyerMeyer 1973 QSAT ∈ PSPACEcomplete. Theorem. PSPACE ⊆ EXPTIME. Pf. Previous algorithm solves QSAT in exponential time; and QSAT is PSPACEcomplete. ▪ Summary. P ⊆ NP ⊆ PSPACE ⊆ EXPTIME. it is known that P ≠ EXPTIME, but unknown which inclusion is strict; conjectured that all are 18PSPACEcomplete problems More PSPACEcomplete problems. Competitive facility location. Natural generalizations of games. Othello, Hex, Geography, RushHour, Instant Insanity Shanghai, gomoku, Sokoban Given a memory restricted Turing machine, does it terminate in at most k steps Do two regular expressions describe different languages Is it possible to move and rotate complicated object with attachments through an irregularly shaped corridor Is a deadlock state possible within a system of communicating processors 19Competitive facility location Input. Graph G = (V, E) with positive edge weights, and target B. Game. Two competing players alternate in selecting nodes. Not allowed to select a node if any of its neighbors has been selected. Competitive facility location. Can second player guarantee at least B units of profit 10 1 5 15 5 1 5 1 15 10 yes if B = 20; no if B = 25 20Competitive facility location Claim. COMPETITIVEFACILITYLOCATION ∈ PSPACEcomplete. Pf. To solve in polyspace, use recursion like QSAT, but at each step there are up to n choices instead of 2. To show that it's complete, we show that QSAT polynomial reduces to it. Given an instance of QSAT, we construct an instance of COMPETITIVE FACILITYLOCATION so that player 2 can force a win iff QSAT formula is true. 21Competitive facility location assume n is odd Construction. Given instance Φ(x , …, x ) = C ∧ C ∧ … C of QSAT. 1 n 1 1 k Include a node for each literal and its negation and connect them. (at most one of x and its negation can be chosen) i i i Choose c ≥ k + 2, and put weight c on literal x and its negation; n–1 n–3 4 2 set B = c + c + … + c + c + 1. (ensures variables are selected in order x , x , …, x ) n n–1 1 n–1 n–3 4 2 As is, player 2 will lose by 1 unit: c + c + … + c + c . n n 10 10 x x n n ⋮ € € 100 100 x x 2 2 10 10 € € x x 1 1 22 € € Competitive facility location Construction. Given instance Φ(x , …, x ) = C ∧ C ∧ … C of QSAT. 1 n 1 1 k Give player 2 one last move on which she can try to win. For each clause C , add node with value 1 and an edge to each of its j literals. Player 2 can make last move iff truth assignment defined alternately by the players failed to satisfy some clause. ▪ n n 10 10 x x n n 1 ⋮ € x ∨ x ∨ x € 1 2 n 100 100 x x clause C j 2 2 € 10 10 € € x x 1 1 23 € €
Website URL
Comment