Space hierarchy theorem

In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. For example, a deterministic Turing machine can solve more decision problems in space "n" log "n" than in space "n". The somewhat weaker analogous theorems for time are the time hierarchy theorems.

The foundation for the hierarchy theorems lies in the intuition thatwith either more time or more space comes the ability to compute morefunctions (or decide more languages). The hierarchy theorems are usedto demonstrate that the time and space complexity classes form ahierarchy where classes with tighter bounds contain fewer languagesthan those with more relaxed bounds. Here we define and prove thespace hierarchy theorem.

The space hierarchy theorems rely on the concept of space-constructible functions. Formally, A function $f:mathbb\{N\}\; longrightarrow\; mathbb\{N\}$ is spaceconstructible if $f(n)\; ge\; log~n$ and there exists a Turing machinewhich computes the function $f(n)$ in space $O(f(n))$ when startingwith an input $1^n$, where $1^n$ represents a string of $n$ $1$s.. Most common functions we work with are space-constructible, including polynomials, exponents, and logarithms.

Statement

For every space constructible function $f:mathbb\{N\}\; longrightarrowmathbb\{N\}$, there exists a language $L$ that is decidable in space$O(f(n))$ but not in space $o(f(n))$.

Proof

The goal here is to define a language that can be decided in space$O(f(n))$ but not space $o(f(n))$. Here we define the language $L$:

$L\; =\; \{~\; (langle\; M\; angle,\; 10^k):\; M\; mbox\{\; does\; not\; accept\}\; (langle\; M\; angle,10^k)\; mbox\{\; using\; space\; \}\; le\; f(|langle\; M\; angle,\; 10^k|)\; ~\; \}$

Now, for any machine $M$ that decides a language in space $o(f(n))$, $L$ will differ in at least one spot from the language of $M$, namely at the value of $(langle\; M\; angle,\; 10^k)$. The algorithm for deciding the language $L$ is as follows:

# On an input $x$, compute $f(|x|)$ using space constructibility, and mark off $f(|x|)$ cells of tape. Whenever an attempt is made to use more than $f(|x|)$ cells, "reject".
# If $x$ is not of the form $langle\; M\; angle,\; 10^k$ for some TM $M$, "reject".
# Simulate $M$ on input $x$ for at most $2^\{f(|x|)\}$ steps (using $f(|x|)$ space). If the simulation tries to use more than $f(|x|)$ space or more than $2^\{f(|x|)\}$ operations, then "reject".
# If $M$ accepted $x$ during this simulation, then "reject"; otherwise, "accept".

Note on step 3: Execution is limited to $2^\{f(|x|)\}$ steps in order to avoid thecase where $M$ does not halt on the input $x$. That is, the case where$M$ consumes space of only $O(f(x))$ as required, but runs forinfinite time.

Comparison and improvements

The space hierarchy theorem is stronger than the analogous time hierarchy theorems in several ways:
* It only requires s(n) to be at least log "n" instead of at least "n".
* It can separate classes with any asymptotic difference, whereas the time hierarchy theorem requires them to be separated by a logarithmic factor.
* It only requires the function to be space-constructible, not time-constructible.

It seems to be easier to separate classes in space than in time. Indeed, whereas the time hierarchy theorem has seen little remarkable improvement since its inception, the nondeterministic space hierarchy theorem has seen at least one important improvement by Viliam Geffert in his 2003 paper "Space hierarchy theorem revised". This paper made several striking generalizations of the theorem:

* It relaxes the space-constructibility requirement. Instead of merely separating the union classes DSPACE(O(s(n)) and DSPACE(o(s(n)), it separates DSPACE(f(n)) from DSPACE(g(n)) where f(n) is an arbitrary O(s(n)) function and g(n) is a computable o(s(n)) function. These functions need not be space-constructible or even monotone increasing.
* It identifies a unary language, or tally language, which is in one class but not the other. In the original theorem, the separating language was arbitrary.
* It does not require s(n) to be at least log "n"; it can be any nondeterministically fully space-constructible function.

Corollaries

Corollary 1

"For any two functions $f\_1$, $f\_2:\; mathbb\{N\}\; longrightarrowmathbb\{N\}$, where $f\_1$(n) is o($f\_2$(n)) and $f\_2$ is spaceconstructible, SPACE($f\_1$(n)) $subset$ SPACE($f\_2$(n))."

This corollary lets us separate various space complexity classes.For any function $n^k$ is space constructible for any naturalnumber k. Therefore for any two natural numbers we canprove SPACE($n^\{k\_1\}$) $subset$ SPACE($n^\{k\_2\}$). We can extendthis idea for real numbers in the following corollary. Thisdemonstrates the detailed hierarchy within the PSPACE class.

Corollary 2

"For any two real numbers 0 $leq\; a\_1\; leq\; a\_2,$ SPACE($n^\{a\_1\}$)$subset$ SPACE($n^\{a\_2\}$)."

Corollary 3

"NL $subset$ PSPACE."

Proof

Savitch's theorem shows that NL $subseteq$ SPACE($log^2n$), while the space hierarchy theorem shows that SPACE($log^2n)\; subsetneq$ SPACE($n$). Thus we get this corollary along with the fact that that TQBF $otin$ NLsince TQBF is PSPACE-complete.

This could also be proven using the non-deterministic space hierarchy theorem to show that NL $subset$ NPSPACE, and using Savitch's theorem to show that PSPACE = NPSPACE.

Corollary 4

PSPACE $subset$ EXPSPACE.

This last corollary shows the existence of decidableproblems that are intractable. In other words their decision procedures must use more than polynomial space.

Corollary 5

There are problems in PSPACE requiring an arbitrarily large exponent to solve; therefore PSPACE does not collapse to DSPACE("n"^"k") for some constant "k".

Corollary 6

L ≠ DSPACE(log² "n"). Since Savitch's theorem implies that NL lies in the latter, we must have either L ≠ NL or NL ≠ DSPACE(log² "n") (although it's commonly believed that both inequalities hold).

References

* Luca Trevisan. [http://www.cs.berkeley.edu/~luca/cs172-04/noteh.pdf Notes on Hierarchy Theorems] . Handout 7. CS172: Automata, Computability and Complexity. U.C. Berkeley. April 26, 2004.
* Viliam Geffert. [http://portal.acm.org/citation.cfm?id=763728 Space hierarchy theorem revised] . "Theoretical Computer Science", volume 295, number 1-3, p.171-187. February 24, 2003.
* Pages 306–310 of section 9.1: Hierarchy theorems.
* Section 7.2: The Hierarchy Theorem, pp.143–146.