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. , where SPACE stands for either DSPACE or NSPACE, and o refers to the little o notation.
- Comment
- enIn 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. , where SPACE stands for either DSPACE or NSPACE, and o refers to the little o notation.
- Has abstract
- enIn 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), , where SPACE stands for either DSPACE or NSPACE, and o refers to the little o notation.
- Is primary topic of
- Space hierarchy theorem
- Label
- enSpace hierarchy theorem
- Link from a Wikipage to an external page
- portal.acm.org/citation.cfm%3Fid=763728
- archive.org/details/introductiontoth00sips
- www.cs.berkeley.edu/~luca/cs172-04/noteh.pdf
- Link from a Wikipage to another Wikipage
- Big O Notation
- Cambridge University Press
- Category:Articles containing proofs
- Category:Structural complexity theory
- Category:Theorems in computational complexity theory
- Computable function
- Computational complexity theory
- Decision problem
- Depth-first search
- Deterministic Turing machine
- DSPACE
- EXPSPACE
- Immerman–Szelepcsényi theorem
- Little o
- Luca Trevisan
- NL (complexity)
- NSPACE
- PSPACE
- Savitch's theorem
- Space-constructible function
- Time hierarchy theorem
- Unary language
- Viliam Geffert
- SameAs
- 4vVak
- m.030thv
- Q7572588
- Space hierarchy theorem
- Teorema de hierarquia de espaço
- 空间阶层定理
- Subject
- Category:Articles containing proofs
- Category:Structural complexity theory
- Category:Theorems in computational complexity theory
- WasDerivedFrom
- Space hierarchy theorem?oldid=1119314445&ns=0
- WikiPageLength
- 14278
- Wikipage page ID
- 663050
- Wikipage revision ID
- 1119314445
- WikiPageUsesTemplate
- Template:Cite book
- Template:Mvar
- Template:Reflist
- Template:Sans-serif
- Template:Short description
- Template:Tmath