CSC 341: May 7, 2007

From CSWiki

Instructor's notes for the class session

NP-completeness proofs for SUBSET-SUM, $\neq$ SAT, and 3DM.

Space complexity classes SPACE $(f (n))$ and NSPACE $(f (n))$ , PSPACE and NPSPACE.

Example 8.4: $\overline{\textit{ALL}_{\mathsf{NFA}}} \in \textrm{SPACE}(n)$ .

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))$ .

[edit]

Study questions

In the proof of Savitch's theorem, Sipser writes: "We select a constant $d$ so that $N$ has no more than $2 d f (n)$ configurations using $f (n)$ tape, where $n$ is the length of $w$ . Then we know that $2 d f (n)$ provides an upper bound on the running time on any branch of $N$ on $w$ ." But how does this follow? Why can't $N$ , for a given input $w$ , enter the same configuration more than once?
To show that $\overline{\textit{ALL}_{\mathsf{NFA}}} \in \textrm{NSPACE}(n)$ , Sipser develops a non-deterministic Turing machine $N$ that decides this language. Yet he says that $\overline{\textit{ALL}_{\mathsf{NFA}}}$ is not known to be a member of NP. Why doesn't $N$ show that $\overline{\textit{ALL}_{\mathsf{NFA}}} \in \textrm{NP}$ ?
Show that, for any polynomial function $f$ , $\textrm{coNSPACE}(f(n)) \subseteq \textrm{PSPACE}$ .

[edit]

Proposed Solutions

The existence of a decider doesn't mean much, since it may run extremely slowly. $A L L N F A$ must be verifiable in polynomial time, and $N$ does not offer that service.
$NL = NSPACE (\log n) \subset NSPACE(f(n)) = coNSPACE(f(n)) \subseteq P \subseteq NP \subseteq PSPACE$

Previous Lecture Next Lecture

Front Door

Retrieved from "http://wiki.cs.grinnell.edu/mediawiki/index.php/CSC_341:_May_7%2C_2007"

CSC 341: May 7, 2007

From CSWiki

Instructor's notes for the class session

Study questions

Proposed Solutions

Views

Personal tools

Navigation

Search

Toolbox