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. The deterministic and nondeterministic space hierarchy theorems state that for all space-constructible functions f(n),
SPACE\left(o(f(n))\right)\subsetneqSPACE(f(n))
Formally, a function
f:N\longrightarrowN
f(n)\gelog~n
f(n)
O(f(n))
1n
1n
For every space-constructible function
f:N\longrightarrow N
O(f(n))
o(f(n))
The goal is to define a language that can be decided in space
O(f(n))
o(f(n))
L=\{~(\langleM\rangle,10k):Musesspace\lef(|\langleM\rangle,10k|)andtime\le
f(|\langleM\rangle,10k|) 2 andMdoesnotaccept(\langleM\rangle, 10k)~\}
For any machine that decides a language in space
o(f(n))
\lef(|\langleM\rangle,10k|)</Math>on<math>(\langleM\rangle,10k)</Math>andwillthereforedifferatitsvalue. Ontheotherhand,{{mvar|L}}isin<math>SPACE(f(n))
f(|x|)
f(|x|)
f(|x|)
\langleM\rangle,10k
2f(|x|)
f(|x|)
f(|x|)
2f(|x|)
Note on step 3: Execution is limited to
2f(|x|)
O(f(x))
The above proof holds for the case of PSPACE, but some changes need to be made for the case of NPSPACE. The crucial point is that while on a deterministic TM, acceptance and rejection can be inverted (crucial for step 4), this is not possible on a non-deterministic machine.
For the case of NPSPACE, needs to be redefined first:
Now, the algorithm needs to be changed to accept by modifying step 4 to:L=\{~(\langleM\rangle,10k):Musesspace\lef(|\langleM\rangle,10k|)andMaccepts(\langleM\rangle, 10k)~\}
can not be decided by a TM using
o(f(n))
o(f(n))
\overlineL
\overlineM
o(f(n))
w=(\langle\overlineM\rangle,10k)
\overlineL
\overlineM
\overlineL
w=(\langle\overlineM\rangle,10k)
\overlineL
\overlineM
\overlineL
The space hierarchy theorem is stronger than the analogous time hierarchy theorems in several ways:
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 generalizations of the theorem:
If space is measured as the number of cells used regardless of alphabet size, then because one can achieve any linear compression by switching to a larger alphabet. However, by measuring space in bits, a much sharper separation is achievable for deterministic space. Instead of being defined up to a multiplicative constant, space is now defined up to an additive constant. However, because any constant amount of external space can be saved by storing the contents into the internal state, we still have .
Assume that f is space-constructible. SPACE is deterministic.
The proof is similar to the proof of the space hierarchy theorem, but with two complications: The universal Turing machine has to be space-efficient, and the reversal has to be space-efficient. One can generally construct universal Turing machines with space overhead, and under appropriate assumptions, just space overhead (which may depend on the machine being simulated). For the reversal, the key issue is how to detect if the simulated machine rejects by entering an infinite (space-constrained) loop. Simply counting the number of steps taken would increase space consumption by about . At the cost of a potentially exponential time increase, loops can be detected space-efficiently as follows:[1]
Modify the machine to erase everything and go to a specific configuration A on success. Use depth-first search to determine whether A is reachable in the space bound from the starting configuration. The search starts at A and goes over configurations that lead to A. Because of determinism, this can be done in place and without going into a loop.
It can also be determined whether the machine exceeds a space bound (as opposed to looping within the space bound) by iterating over all configurations about to exceed the space bound and checking (again using depth-first search) whether the initial configuration leads to any of them.
For any two functions
f1
f2:N\longrightarrow N
f1(n)
o(f2(n))
f2
SPACE(f1(n))\subsetneqSPACE(f2(n))
This corollary lets us separate various space complexity classes.For any natural number k, the function
nk
k1<k2
k1 | |
SPACE(n |
)\subsetneq
k2 | |
SPACE(n |
)
Savitch's theorem shows that
NL\subseteqSPACE(log2n)
SPACE(log2n)\subsetneqSPACE(n)
This could also be proven using the non-deterministic space hierarchy theorem to show that NL ⊊ NPSPACE, and using Savitch's theorem to show that PSPACE = NPSPACE.
This last corollary shows the existence of decidable problems that are intractable. In other words, their decision procedures must use more than polynomial space.
There are problems in requiring an arbitrarily large exponent to solve; therefore does not collapse to (nk) for some constant k.
SPACE(n) ≠ PTIME.
To see it, assume the contrary, thus any problem decided in space
O(n)
O(nc)
L
O(nb)
O((nb)c)=O(nbc)
P:=cupk\inNDTIME(nk)
cupk\inNDTIME(nbk)\subseteqP
L\inP
b,SPACE(nb)\subseteqP\subseteqSPACE(n)
SPACE(n2)\not\subseteqSPACE(n)
P\not\subseteqSPACE(n)
SPACE(n)\not\subseteqP
SPACE(n)
P
NSPACE(n)