Skip to content

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) \geq 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