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 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.
Read more about Space Hierarchy Theorem: Statement, Proof, Comparison and Improvements, Refinement of Space Hierarchy
Famous quotes containing the words space, hierarchy and/or theorem:
“What a phenomenon it has been—science fiction, space fiction—exploding out of nowhere, unexpectedly of course, as always happens when the human mind is being forced to expand; this time starwards, galaxy-wise, and who knows where next.”
—Doris Lessing (b. 1919)
“In the world of the celebrity, the hierarchy of publicity has replaced the hierarchy of descent and even of great wealth.”
—C. Wright Mills (1916–1962)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)