CSC 341: May 9, 2007

From CSWiki

1 Instructor's notes for the class session
2 Study questions
- 2.1 Proposed Solutions

Instructor's notes for the class session

Savitch's theorem

For any function $f: \mathcal{N} \rightarrow \mathcal{R}^+$ , where $f(n) \ge n$ , $\textrm{NSPACE}(f(n)) \subseteq \textrm{SPACE}(f^2(n))$ .

The proof is by construction: Given a non-deterministic Turing machine $N$ that decides a language A in $f (n)$ space, we can construct a deterministic Turing machine that decides the same language in $f 2 (n)$ space. The idea is to use a divide-and-conquer algorithm.

First, we modify $N$ so that it has only one acceptance configuration, $q_\mathrm{accept}\textvisiblespace$ . This adds at most 1 to its space complexity; if necessary, we incorporate this increment into the definition of $f$ , which does not affect its order of complexity.

Then we arrange for our deterministic Turing machine to compute an upper bound on the number of distinct configurations that $N$ could be in during a run of the program, on an input of length $n$ , given that only $f (n)$ tape cells will be used. If we assume, in the worst case, that the read-write head might be on any cell of the tape, with the machine of its states, and the tape contents being any string from the tape alphabet, there are only $|Q| \times f(n) \times |\Sigma|^{f(n)}$ possible configurations; as Sipser points out, this implies that there is some constant $d$ such that $2 d f (n)$ will serve as an appropriate upper bound, and such a $d$ can be computed from $n$ , $| Q |$ , and $| Σ |$ .

Once we have determined this upper bound, the question of whether $N$ accepts a string $w$ of length $n$ reduces to the question of whether $N$ can go through a series of $2 d f (n)$ transitions that take it from the start configuration $q_0\,w$ to the accepting configuration. We design our deterministic Turing machine to perform this test by executing a recursive procedure, described at the top of page 307: If the number of transitions available is 1, we look to see whether the initial and final configurations are either identical or differ in a way that accurately reflects a single transition in $N$ . Otherwise, we divide the problem into two subproblems by testing, for each possible configuration $c m$ , whether $N$ can get for the initial configuration to $c m$ in half the specified number of transitions, and from $c m$ to the final configuration in half the specified number of transitions, accepting if both are possible.

To manage the recursion, we'll need to separate the tape into regions of size $O (f (n))$ , one for each level of recursion, so that the status of each problem that has been started but not yet finished can be retained while its subproblems are addressed. However, the number of levels of recursion cannot be greater than $d f (n)$ . So the total space complexity of our simulator is $O (f 2 (n))$ , as required.

[edit]

PSPACE = NPSPACE

We can form the grand union of all the $SPACE(n k)$ classes to obtain PSPACE, the set of languages that can be decided by deterministic Turing machines with polynomial space-complexity functions. Similarly, the grand union of all the $NSPACE(n k)$ classes is NPSPACE. But Savitch's theorem shows that $PSPACE = NPSPACE$ , since the square of any polynomial function is itself polynomial.

Since the space complexity of any decider is bounded above by its time complexity (it can't use cells that it doesn't have time to reach!), $\textrm{P} \subseteq \textrm{PSPACE}$ and $\textrm{NP} \subseteq \textrm{NPSPACE}$ , so that $\textrm{NP} \subseteq \textrm{PSPACE}$ .

[edit]

PSPACE-completeness

A language is PSPACE-hard if every language in PSPACE is polynomial-time reducible to it. It is PSPACE-complete if it is a member of PSPACE and is PSPACE-hard. There is a modest collection of languages that are known to be PSPACE-complete, of which the leading example is TQBF, the set of true, fully quantified Boolean formulas. The construction showing that TQBF is PSPACE-hard incorporates some ideas from the proof of the Cook-Levin theorem and some from the proof of Savitch's theorem.

Sipser offers two other PSPACE-complete languages, FORMULA-GAME and GG ("generalized geography"). The first turns out to be just another name for TQBF; the second is proved PSPACE-complete by showing membership in PSPACE and then providing a polynomial-time reduction of TQBF to GG.

[edit]

Study questions

Is the fully quantified Boolean formula $\forall x \forall y \exists z [(x \wedge \overline{z}) \vee (z \wedge \overline{y})]$ true or false? Justify your answer.
What "generalized geography" graph does the mapping function developed in Sipser's proof of Theorem 8.14 yield when given the formula in the preceding study question, as an instance of FORMULA-GAME?
Prove that, if there is a language L that is both PSPACE-complete and NP-complete, then $PSPACE = NP$ .

[edit]

Proposed Solutions

False - if x is false and y is true, no choice of z will make the statement true.
Assume that $\textrm{PSPACE} \neq \textrm{NP}$ and there is a language G that is a member of $NP$ , but not a member of $PSPACE$ . If L exists, then $G \leq_P L$ because all members of $NP$ are polynomial time reducible to any NP-complete language. But if $G \leq_P L$ and L is PSPACE-complete, then G must also be a member of $PSPACE$ , because any language that are polynomial time reducible to a PSPACE-complete language are in $PSPACE$ . Because this holds true for any member of $NP$ , then the existence of L would mean that $PSPACE = NP$ .