25. Space Complexity

Apr 14, 2022

Space complexity $f(n)$:

PSPACE(f(n))

All deterministic decidable languages that use $O(f(n))$ space.

• for deterministic Turing machine: maximum number of cells that the machine scans on any input string of size $n$ => total space used $f(n)$.

NSPACE(f(n))

all non-deterministic decidable languages that use $O(f(n))$ space.

• for non-deterministic Turing machine: maximum number of cells that the machine scans on any input string of size $n$ in any computation path

Note: space is always bounded by time.

Examples:

• SAT is a linear space problem -- given a formula, we can check in linear space every possible assignment to variables.

• An interesting problem: ALL${}_{NFA}$ -- it is not known if it is in NP, however the problem is in NSPACE(n)

---

Savitch's Theorem

NSPACE($f(n)$) $\subseteq$ SPACE($f^2(n)$)   $f(n)\ge n$

---

Given NTWM $N$ that decides in $f(n)$ space, build DTM $M$ that decides in $O(f^2(n))$ space. Assume NTM $N$ clears the tape when it accepts and enters a special configuration $c_{\text{accept}}$. Key idea: CANYIELD$(c_1,c_2,t)$ => does configuration $c_1$ yield $c_2$ in $t$ steps?

=> recursion: CANYIELD$(c_1,c_2,t)$ => CANYIELD$(c_1,c_m,t/2)$ => CANYIELD$(c_m,c_2,t/2)$

Possibilities for $c_m:2^{df(n)}$

Run CANYIELD$(c_{\text{start}},c_{\text{accept}},2^{df(n)})$

• depth of search tree: $\log (2^{df(n)})=O(f(n))$
• information stored at each tree level: $O(f(n))$
• total space: $O(f^2(n))$

Difficulty: $f(n)$ is not known -- guess.

Check also if space used by NTM is more than $f(n)$.

---

${\displaystyle \text{PSPACE}=\bigcup _k\text{SPACE}(n^k)}$

${\displaystyle \text{NPSPACE}=\bigcup _k\text{NSPACE}(n^k)}$

• Trivially: PSPACE $\subseteq$ NPSPACE
• From Savitch's theorem: NPSPACE $\subseteq$ PSPACE

=> PSPACE = NPSPACE

P $\subseteq$ NP $\subseteq$ PSPACE = NPSPACE $\subseteq$ EXPTIME