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.
Contents
- Statement
- Proof
- Comparison and improvements
- Refinement of space hierarchy
- Corollary 1
- Corollary 2
- Corollary 3
- Corollary 4
- Corollary 5
- References
The foundation for the hierarchy theorems lies in the intuition that with either more time or more space comes the ability to compute more functions (or decide more languages). The hierarchy theorems are used to demonstrate that the time and space complexity classes form a hierarchy where classes with tighter bounds contain fewer languages than those with more relaxed bounds. Here we define and prove the space 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),
where SPACE stands for either DSPACE or NSPACE, and o refers to the little o notation.
Statement
Formally, a function
For every space-constructible function
Proof
The goal here is to define a language that can be decided in space
Now, for any machine M that decides a language in space
- On an input x, compute
f ( | x | ) using space-constructibility, and mark offf ( | x | ) cells of tape. Whenever an attempt is made to use more thanf ( | x | ) cells, reject. - If x is not of the form
⟨ M ⟩ , 10 k - Simulate M on input x for at most
2 f ( | x | ) f ( | x | ) space). If the simulation tries to use more thanf ( | x | ) space or more than2 f ( | x | ) - If M accepted x during this simulation, then reject; otherwise, accept.
Note on step 3: Execution is limited to
The above proof holds for the case of PSPACE whereas we must make some change for the case of NPSPACE. The crucial point is that while on a deterministic TM we may easily invert acceptance and rejection (crucial for step 4), this is not possible on a non-deterministic machine.
For the case of NPSPACE we will first modify step 4 to:
- If M accepted x during this simulation, then accept; otherwise, reject.
We will now prove by contradiction that L can not be decided by a TM using
Assuming L can be decided by a TM using
Here lies the contradiction, therefore our assumption must be false:
- If
w = ( ⟨ M ¯ ⟩ , 10 k ) (for some large enough k) is not in L then M will accept it, thereforeM ¯ - If
w = ( ⟨ M ¯ ⟩ , 10 k ) (for some large enough k) is in L then M will reject it, thereforeM ¯
Comparison and improvements
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:
Refinement of space hierarchy
If space is measured as the number of cells used regardless of alphabet size, then
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
Modify the machine to erase everything and to 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. Also (but this is not necessary for the proof), to determine whether the machine exceeds the space bound (as opposed to looping within the space bound), we can iterate over all configurations about to exceed the space bound and check (again using depth-first search) whether the initial configuration leads to any of them.
Corollary 1
For any two functions
This corollary lets us separate various space complexity classes. For any function
Corollary 2
For any two nonnegative real numbers
Corollary 3
NL ⊊ PSPACE.Proof
Savitch's theorem shows that
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.
Corollary 4
PSPACE ⊊ EXPSPACE.This last corollary shows the existence of decidable problems 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(nk) for some constant k.