算法设计与分析笔记0x0F —— PSPACE

P Decision problems solvable in polynomial time.
PSPACE Decision problems solvable in polynomial space.

  • P PSPACE
  • 3-SAT is in PSPACE
  • NP PSPACE

Quantifies Satisfiability

  • QSAT Let Φ(x1, …, xn) be a Boolean CNF formula. Is the following proposional formula true?

x1x2x3x4…∀xn − 1xnΦ(x1, …, xn)

  • Amy picks truth value for x1, then Bob for x2, then Amy for x3, and so on. Can Amy satisfy Φ no matter what Bob does?
  • 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.

Planning Problem

  • Conditions. Set C = {C1, …, Cn}
  • Initial configuration. Subset c0 ⊆ C of conditions initially satisfied.
  • Goal configuration. Subset $c* \subseteq C$ of conditions we seek to satisfy.
  • Operators. Set O = {O1, …, Ok}
    • To invoke operator Oi, must satisfy certain prereq conditions.
    • After invoking Oi certain conditions become true, and certain conditions become false.
  • PLANNING. Is it possible to apply sequence of operators to get from initial configuration to goal configuration?

8-Puzzle

九格的板块,缺失一格,每次可以移动到空白处。

  • Conditions. Cij, $1 \leq i$, j ≤ 9, where Cij means 数字i在方块9
  • Initial state. c0 = {C11, C22, …, C66, C78, C87, C99}
  • Good state. $c* = {C_{11}, C_{22}, …, C_{66}, C_{77}, C_{88}, C_{99}}$
  • Operators.
    • Precondition to apply Oi = {C11, C22, …, C66, C78, C87, C99}
    • After invoking Oi, conditions C79 and C98 become true.
    • After invoking Oi, conditions C78 and C99 become true.
  • Configuration graph G
    • Include node for each of 2n 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 c0 to $c*$ in configuration graph?
  • Claim. PLANNING in EXPTIME.
    • Run BFS to find path from c0 to $c*$ in configuration graph.
  • Configuration graph can have 2n nodes, and shortest path can be of length = 2n − 1.
  • Theorem PLANNING is in PSPACE.
  • Pf L = 2n − 1, where n is number of conditions
    • Suppose there is a path from c1 to c2 of length L.
    • Path from c1 to midpoint and from midpoint to c2 are each L/2.
    • Enumerate all possible midpoints.
    • Apply recursively. Depth of recursion = log2L.

PSPACE-Complete

Y is PSPACE-complete if:

  1. Y is in PSPACE
  2. For every problem X in PSPACE, X p Y

  • QSAT is PSPACE-complete.
  • PSPACE EXPTIME
    • Previous algorithm solves QSAT in exponential time, and QSAT is PSPACE-complete.
  • Summary P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

Competitive Facility Location

  • Input. Graph with positive node weights, and target number 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?
  • Claim. COMPETITIVE-FACILITY is PSPACE-complete.
  • Pf.
    • To solve it in poly-space, 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-FACILITY such that player 2 can force a win iff QSAT formula is false.
Construction Given instance Φ(x1, …, xn)=C1 ∩ C2 ∩ …Ck of QSAT.

  • Include a node for each literal and its negation and connect them.
    • at most one of xi and its negation can be chosen
  • Choose a large constant c (e.g., c k+2), and put weight cn − i + 1 on literal xi and its negation; set B = cn − 1 + cn − 3 + … + c4 + c2 + 1.
    • This ensures variables are selected in order x1, x2, …, xn.
  • As is, player 2 will lose by 1 unit: $c^{n-1} + c^{n-3} + … + c^4 + c^2$.
  • Give player 2 one last move on which she can try to win.
  • For each clause Cj, add node with value 1 and an edge to each of its literals.
  • Player 2 can make last move iff truth assignment defined alternately by the players failed to satisfy some clause, i.e.,
    • x1x2x3x4…∃xn − 1xn¬Φ(x1, …, xn)⇔∃x1x2x3x4…∀xn − 1xnΦ(x1, …, xn)

Leave a Reply

Your email address will not be published.