PSPACE Completeness

PDF of Prof. Santosh’s handwritten notes is here.

Recall PSPACE = \bigcup_k SPACE(n^k)

Analogously to NP-completeness, we can define a notion of being PSPACE-complete. L is PSPACE-complete if

  1. L \in PSPACE
  2. L is PSPACE-Hard i.e. for all L' \in PSPACE, L' \hookrightarrow_P L

Note that in point 2 above, the reduction should be polynomial time so that if L \in P and PSPACE-complete, then PSPACE=P.

Definition: Totally Quantified Boolean Formula (TQBF) is the language of SAT instances where every literal has a quantifier (either \exists or \forall) and the formula has a satisfying assignment.

Example: \exists x_1 \forall x_2 \exists x_3 (x_1 \wedge \bar{x_2} \wedge x_3)

Theorem: TQBF is PSPACE-Complete

Proof:

\mathbf{TQBF \in PSPACE}

CHECK(F(x_1, x_2, \dots, x_n))

  • If all variables are set, return value of F on this assignment
  • If \exists x_1: return CHECK(F(x_1=0, x_2, \dots, x_n)) \vee CHECK(F(x_1=1, x_2, \dots, x_n))
  • Else \forall x_1: return CHECK(F(x_1=0, x_2, \dots, x_n)) \wedge CHECK(F(x_1=1, x_2, \dots, x_n))

The above formula decides TQBF in polynomial space as the depth of the recursion is at most n and each level of recursion uses space proportional to the size of the formula F.

TQBF is PSPACE-Hard i.e. \forall L \in PSPACE, there exists a polynomial time reduction from L to TQBF

Let L \in PSPACE. Thus, \exists TM M that decides L using polynomial space.

Consider the configurations of M. Let C_{start} be the starting configuration and let C_{accept} be an accepting configuration.

If M uses O(n^k) space, the graph consisting of configurations of M will have O(exp(n^k)) vertices. Thus, the path from C_{start} to C_{accept} may involve an exponential number of nodes. Let’s attempt to use the PATH algorithm from the proof of Savitch’s theorem.

PATH(u,v,t):

  • If t=0, check if u = v
  • If t=1, check if there is an edge from u to v
  • Check \exists w: PATH(u,w,\frac{t}{2}) \wedge PATH(w,v,\frac{t}{2})

The above algorithm has at most O(\log{(exp(n^k)}) = O(n^k) levels of recursion, however, the size of the formula doubles at each level. So instead, let’s try to use the \forall quantifier as well.

\exists w \forall (x,y) \in \{(u,w), (w,v)\} PATH(x,y,\frac{t}{2})

We need to write (x,y) \in \{(u,w), (w,v)\} as a Boolean formula.

(x,y) = (u,w) \vee (x,y) = (w,v) \Rightarrow F

Observe the following:

  • (x,y) = (u,v) \Leftrightarrow (x = u) \wedge (y = v) \Leftrightarrow ((x \wedge u) \vee (\bar{x} \wedge \bar{u})) \wedge ((y \wedge v) \vee (\bar{y} \wedge \bar{v}))
  • (A \Rightarrow B) \Leftrightarrow (\bar{A} \vee B)

Using the relations above, we can transform the formula into a quantified boolean formula and apply this recursively.

Thus, there are O(n^k) levels of recursion and the size of the formula increases by O(n^k) at each level. Thus, the size of the final formula and the time used to derive it is O(n^{2k}).

Hence, given any language L \in PSPACE, we can obtain an equivalent TQBF that has size polynomial in the size of the input, and the construction takes polynomial time.

Thus, TQBF is PSPACE-Complete.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s