The class of decision problems solvable by a Turing machine in space O(f(n)).
The Space Hierarchy Theorem: For constructible f(n) greater than logn, DSPACE(f(n)) is strictly contained in DSPACE(f(n) log(f(n))) [HLS65].
For space constructible f(n), strictly contains DTIME(f(n)) [HPV77].
DSPACE(n) does not equal NP (though we have no idea if one contains the other)!
See also: NSPACE(f(n)).
Defined in [Sch16]. Let and where is applied to itself times. For example , , etc. Then define, , note that this has the same growth rate as where A is the Ackermann function. This class is equal to DTIME(Fω(p(n))) over all primitive-recursive functions p(n). The class remains unchanged if we replace DTIME with NTIME or DSPACE.
Strictly contains ELEMENTARY, Tower, and PR. Is strictly contained in R.
The relationship between this class and PR is analogous to the relationship between Tower and ELEMENTARY. That is, Ack contains problems "barely" outside of PR and, unlike PR, has complete problems.
The reachability problems for Petri nets [Ler22] and vector addition systems [CO22] are complete for this class under primitive recursive reductions, as well as the problem of navigating robots through a maze of gadgets with spawner and destroyer nodes [Ani+23].
The class of decision problems solvable in O(f(n))-space with error probability at most 1/3, by a Turing machine that halts on every input and every random tape setting.
Contains RHSPACE(f(n)).
Is contained in DSPACE(f(n)3/2) [SZ95].
Equals DSPACE(22O(n)).
Is not contained in BQP/qpoly [NY03].
Equals DSPACE(2O(n)).
If E = ESPACE then P = BPP [HY84].
Indeed if E has nonzero measure in ESPACE then P = BPP [Lut91].
ESPACE is not contained in P/poly [Kan82].
Is not contained in BQP/mpoly [NY03].
See also: EXPSPACE.
Equals the union of DSPACE(2p(n)) over all polynomials p.
See also: ESPACE.
Given a first-order statement about real numbers, involving only addition and comparison (no multiplication), we can decide in EXPSPACE whether it's true or not [Ber80].
The class of decision problems that can be proven to be solvable in O(f(n)) space on a deterministic Turing machine, from the axioms of formal system F.
Defined in [Har78].
See also F-TIME(f(n)). The results about F-TAPE mirror those about F-TIME, but in some cases are sharper.
Same as NPSPACE, but with f(n)-space (for some constructible function f) rather than polynomial-space machines.
Contained in DSPACE(f(n)2) [Sav70], and indeed RevSPACE(f(n)2) 95|[CP95].
NSPACE(nk) is strictly contained in NSPACE(nk+ε) for ε>0 [Iba72] (actually the hierarchy theorem is stronger than this, but pretty technical to state).
Equals DSPACE((log n)c).
In contrast to L, which is contained in P, it is not known if polyL is contained in P or vice versa (or if none of the inclusions hold). On the other hand, we do know that polyL does not equal P, since (for example) polyL does not have complete problems under many-to-one logspace reductions.
Has the same relation to DSPACE(f(n)) as PP does to P. The Turing machine has to halt on every input and every setting of the random tape.
Has the same relation to DSPACE(f(n)) as PP does to P. The Turing machine has to halt with probability 1 on every input.
Contained in DSPACE(f(n)2) [BCP83].
Equals PrHSPACE(f(n)) [Jun85].
Equals DSPACE(2polylog(n)).
According to [BG94], Beigel and Feigenbaum and (independently) Krawczyk showed that QPSPACE is not contained in Check.
The class of decision problems solvable by deterministic finite automata (DFAs).
Equals the class solvable by nondeterministic finite automata (NDFAs).
Equals DSPACE(O(1)) [She59], which equals DSPACE(o(log log n)) [HLS65].
Includes, i.e., "Is the parity of the input odd?," but not "Are the majority of bits in the input 1's?" This is sometimes expressed as "finite automata can't count."
Contained in NC1.
See e.g. [Koz97], [Gur89] for basic results on regular languages.
The class of decision problems solvable in space O(f(n)) by a reversible Turing machine (a deterministic Turing machine for which every configuration has at most one immediate predecessor).
Was shown to equal DSPACE(f(n)) [LMT97].
The class of problems solvable by a nondeterministic Turing machine in logarithmic space, such that
Defined in [LP82].
The undirected s-t connectivity problem (USTCON: is there a path from vertex s to vertex t in a given undirected graph?) is complete for SL, under L-reductions.
SL contains L, and is contained in NL.
It follows from [AKL+79] that SL is contained in L/poly.
[KW93] showed that SL is contained in ⊕L, as well as ModkL for every prime k.
SL is also contained in DSPACE(log3/2n) [NSW92], and indeed in DSPACE(log4/3n) [ATW+00].
[NT95] showed that SL equals coSL, and furthermore that SLSL = SL (that is, the symmetric logspace hierarchy collapses).
Reingold ultimately showed that SL = L [Rei04], even relative to an oracle. This subsumes many of the earlier results.
