space hierarchy theorem
theorem
≈ 6 min read
space hierarchy theorem. encyclopegia.org, snapshot space-hierarchy-theorem-851459-699b5bdee0debdba. /a/space-hierarchy-theorem
Names in other languages
- PortuguêsTeorema de hierarquia de espaço
- azMəkan iyerarxiyası teoremləri
- Englishspace hierarchy theorem
- עבריתמשפט ההיררכיה במקום
- 日本語領域階層定理
- 中文空間階層定理
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 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) and all g(n) \in o(f(n)) , \mathsf{SPACE}(g(n)) \subsetneq \mathsf{SPACE}(f(n)) , where SPACE stands for either DSPACE or NSPACE, and refers to the little o notation. L = \{~ (\langle M \rangle, 10^k): M \mbox{ uses space } \le f(|\langle M \rangle, 10^k|) \mbox{ and time } \le 2^{f(|\langle M \rangle, 10^k|)} \mbox{ and } M \mbox{ does not accept } (\langle M \rangle, 10^k) ~ \} For any machine that decides a language in space o(f(n)) , will differ in at least one spot from the language of .
Namely, for some large enough , will use space \le f(|\langle M \rangle, 10^k|) on (\langle M \rangle, 10^k) and will therefore differ at its value. On the other hand, is in \mathsf{SPACE}(f(n)) . The algorithm for deciding the language is as follows: On an input , 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 is not of the form \langle M \rangle, 10^k for some TM , reject. Simulate on input 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 accepted during this simulation, then reject; otherwise, accept. Note on step 3: Execution is limited to 2^{f(|x|)} steps in order to avoid the case where does not halt on the input .
That is, the case where consumes space of only O(f(x)) as required, but runs for infinite time. 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: L = \{~ (\langle M \rangle, 10^k): M \mbox{ uses space } \le f(|\langle M \rangle, 10^k|) \mbox{ and } M \mbox{ accepts } (\langle M \rangle, 10^k) ~ \} Now, the algorithm needs to be changed to accept by modifying step 4 to: If accepted during this simulation, then accept; otherwise, reject. can not be decided by a TM using o(f(n)) cells. Assuming can be decided by some TM using o(f(n)) cells, and following from the Immerman–Szelepcsényi theorem, \overline L can also be determined by a TM (called \overline M ) using o(f(n)) cells.
Here lies the contradiction, therefore the assumption must be false: If w = (\langle \overline M \rangle, 10^k) (for some large enough ) is not in \overline L then will accept it, therefore \overline M rejects , therefore is in \overline L (contradiction). If w = (\langle \overline M \rangle, 10^k) (for some large enough ) is in \overline L then will reject it, therefore \overline M accepts , therefore is not in \overline L (contradiction).
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. To see it, assume the contrary, thus any problem decided in space O(n) is decided in time O(n^c) , and any problem L decided in space O(n^b) is decided in time O((n^b)^c)=O(n^{bc}) .
Now \mathsf{P}:=\bigcup_{k\in\mathbb N}\mathsf{DTIME}(n^k) , thus P is closed under such a change of bound, that is \bigcup_{k\in\mathbb N}\mathsf{DTIME}(n^{bk})\subseteq\mathsf{P} , so L\in\mathsf{P} . This implies that for all b, \mathsf{SPACE}(n^b)\subseteq\mathsf{P}\subseteq\mathsf{SPACE}(n) , but the space hierarchy theorem implies that \mathsf{SPACE}(n^2)\not\subseteq\mathsf{SPACE}(n) , and Corollary 6 follows.
Note that this argument neither proves that \mathsf{P}\not\subseteq\mathsf{SPACE}(n) nor that \mathsf{SPACE}(n)\not\subseteq\mathsf{P} , as to reach a contradiction we used the negation of both sentences, that is we used both inclusions, and can only deduce that at least one fails. It is currently unknown which fail(s) but conjectured that both do, that is that \mathsf{SPACE}(n) and \mathsf{P} are incomparable -at least for deterministic space.
This question is related to that of the time complexity of (nondeterministic) linear bounded automata which accept the complexity class \mathsf{NSPACE}(n) ( as context-sensitive languages, CSL); so by the above CSL is not known to be decidable in polynomial time -see also Kuroda's two problems on LBA. Viliam Geffert. 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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1361697963 under CC BY-SA 4.0; modifications have been made.