Space hierarchy theorem
Encyclopedia
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 problem
s in space n log n than in space n. The somewhat weaker analogous theorems for time are the time hierarchy theorem
s.
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
.
is space-constructible if 
and there exists a Turing machine
which computes the function
in space 
when starting
with an input
, where 
represents a string of 
s. Most of the common functions that we work with are space-constructible, including polynomials, exponents, and logarithms.
For every space-constructible function
, there exists a language 
that is decidable in space
but not in space 
.
but not space 
. Here we define the language 
:
Now, for any machine
that decides a language in space 
, 
will differ in at least one spot from the language of 
, namely at the value of 
. The algorithm for deciding the language 
is as follows:
Note on step 3: Execution is limited to
steps in order to avoid the
case where
does not halt on the input 
. That is, the case where
consumes space of only 
as required, but runs for
infinite time.
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 striking generalizations of the theorem:
, 
, where 
(n) is o(
(n)) and 
is space-constructible, SPACE(
(n)) 
SPACE(
(n)).
This corollary lets us separate various space complexity classes.
For any function
is space-constructible for any natural
number k. Therefore for any two natural numbers
we can
prove SPACE(
) 
SPACE(
). We can extend
this idea for real numbers in the following corollary. This
demonstrates the detailed hierarchy within the PSPACE class.
SPACE(
)
SPACE(
).
shows that NL
SPACE(
), while the space hierarchy theorem shows that SPACE(
SPACE(
). Thus we get this corollary along with the fact that TQBF 
NL
since TQBF is PSPACE-complete.
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.
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.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, 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 problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s in space n log n than in space n. The somewhat weaker analogous theorems for time are the time hierarchy theorem
Time hierarchy theorem
In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems...
s.
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
DSPACE
In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a...
or NSPACE
NSPACE
In computational complexity theory, the complexity class NSPACE is the set of decision problems that can be solved by a non-deterministic Turing machine using space O, and unlimited time. It is the non-deterministic counterpart of DSPACE.Several important complexity classes can be defined in terms...
.
Statement
Formally, a function is space-constructible if and there exists a Turing machinewhich computes the function
in space when startingwith an input
, where represents a string of s. Most of the common functions that we work with are space-constructible, including polynomials, exponents, and logarithms.For every space-constructible function
, there exists a language that is decidable in space but not in space .Proof
The goal here is to define a language that can be decided in space but not space . Here we define the language :
Now, for any machine
that decides a language in space , will differ in at least one spot from the language of , namely at the value of . The algorithm for deciding the language is as follows:- On an input
, compute 
using space-constructibility, and mark off 
cells of tape. Whenever an attempt is made to use more than 
cells, reject. - If
is not of the form 
for some TM 
, reject. - Simulate
on input 
for at most 
steps (using 
space). If the simulation tries to use more than 
space or more than 
operations, then reject. - If
accepted 
during this simulation, then reject; otherwise, accept.
Note on step 3: Execution is limited to
steps in order to avoid thecase where
does not halt on the input . That is, the case where consumes space of only as required, but runs forinfinite time.
Comparison and improvements
The space hierarchy theorem is stronger than the analogous time hierarchy theorems in several ways:- It only requires s(n) to be at least log n instead of at least n.
- It can separate classes with any asymptotic difference, whereas the time hierarchy theorem requires them to be separated by a logarithmic factor.
- It only requires the function to be space-constructible, not time-constructible.
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 striking generalizations of the theorem:
- It relaxes the space-constructibility requirement. Instead of merely separating the union classes DSPACE(O(s(n)) and DSPACE(o(s(n)), it separates DSPACE(f(n)) from DSPACE(g(n)) where f(n) is an arbitrary O(s(n)) function and g(n) is a computableComputable functionComputable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
o(s(n)) function. These functions need not be space-constructible or even monotone increasing. - It identifies a unary language, or tally language, which is in one class but not the other. In the original theorem, the separating language was arbitrary.
- It does not require s(n) to be at least log n; it can be any nondeterministically fully space-constructible function.
Corollary 1
For any two functions, , where (n) is o((n)) and is space-constructible, SPACE((n)) SPACE((n)).This corollary lets us separate various space complexity classes.
For any function
is space-constructible for any naturalnumber k. Therefore for any two natural numbers
we canprove SPACE(
) SPACE(). We can extendthis idea for real numbers in the following corollary. This
demonstrates the detailed hierarchy within the PSPACE class.
Corollary 2
For any two real numbers 0 SPACE() SPACE().Proof
Savitch's theoremSavitch's theorem
In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, states that for any function ƒ ≥ log,...
shows that NL
SPACE(), while the space hierarchy theorem shows that SPACE( SPACE(). Thus we get this corollary along with the fact that TQBF NLsince TQBF is PSPACE-complete.
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
PSPACEPSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
EXPSPACEEXPSPACE
In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O space, where p is a polynomial function of n...
.
This last corollary shows the existence of decidable
problems that are intractable. In other words their decision procedures must use more than polynomial space.