The class of decision problems solvable by a Turing machine in time . Note that some authors choose to call this class TIME.
Of great relevance to DTIME is the Time Hierarchy Theorem: For any constructible function greater than , DTIME() is strictly contained in DTIME() [HS65]. As a corollary, P ⊂ EXP.
For any space constructible , DTIME() is strictly contained in DSPACE() [HPV77].
Also, DTIME() is strictly contained in NTIME() [PPS+83] (this result does not work for arbitrary ).
For any constructible superpolynomial , DTIME() with PP oracle is not in P/poly (see [All96]).
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].
Roughly, the class of continuous problems solvable by an ordinary differential equation (ODE) with convergence time logarithmic in the size of the input. The vector field of the ODE is specified by an NC1 formula, with n parameters that represent the input. The point to which the ODE converges (assuming it does) is the output.
Defined in [BSF02], which should be consulted for more details.
[BSF02] show that finding the maximum of n integers is in CLOG. Thus, CLOG is best thought of as the continuous-time analog of NC1, not of DTIME(log n).
Contained in CP.
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)).
Equals DTIME(2O(n)).
Does not equal NP [Boo72] or PSPACE [Boo74] relative to any oracle. However, there is an oracle relative to which E is contained in NP (see ZPP), and an oracle relative to PSPACE is contained in E (by equating the former with P).
There exists a problem that is complete for E under polynomial-time Turing reductions but not polynomial-time truth-table reductions [Wat87].
Problems hard for BPP under Turing reductions have measure 1 in E [AS94].
It follows that, if the problems complete for E under Turing reductions do not have measure 1 in E, then BPP does not equal EXP.
[IT89] gave an oracle relative to which E = NE but still there is an exponential-time binary predicate whose corresponding search problem is not in E.
[BF03] gave a proof that if E = NE, then no sparse set is collapsing, where they defined a set to be collapsing if and if for all such that and are Turing reducible to each other, and are many-to-one reducible to each other.
Contrast with EXP.
Equals DTIME(22O(n)) (though some authors alternatively define it as being equal to DTIME(2O(2n))).
EE = BPE if and only if EXP = BPP [IKW01].
Equals DTIME(222O(n)).
In contrast to the case of EE, it is not known whether EEE = BPEE implies EE = BPE [IKW01].
Equals DTIME(22p(n)) for p a polynomial.
Also known as 2-EXP.
Contains EE, and is contained in NEEXP.
Equals the union of DTIME(2n), DTIME(22n), DTIME(222n), and so on.
Equals the union of DTIME(2p(n)) over all polynomials p.
If EXP is in P/poly then EXP = MA [BFL91].
Problems complete for EXP under many-one reductions have measure 0 in EXP [May94], [JL95].
There exist oracles relative to which
[BT04] show the following rather striking result: let A be many-one complete for EXP, and let S be any set in P of subexponential density. Then A-S is Turing-complete for EXP.
[SM03] show that if EXP has circuits of polynomial size, then P can be simulated in MAPOLYLOG such that no deterministic polynomial-time adversary can generate a list of inputs for a P problem that includes one which fails to be simulated. As a result, EXP ⊆ MA if EXP has circuits of polynomial size.
[SU05] show that EXP NP/poly implies EXP P||NP/poly.
In descriptive complexity EXPTIME can be defined as SO() which is also SO(LFP)
The class of decision problems that can be proven to be solvable in O(f(n)) time on a deterministic Turing machine, from the axioms of formal system F.
Defined in [Har78], where the following was also shown:
See also F-TAPE(f(n)).
For functions and , we say that tuple , where is a language and is a distribution of problem instances, if there exists a heuristic deterministic algorithm such that for all in the support of , runs in time bounded by and with failure probability bounded by [BT06].
The class of decision problems expressible in logical form as
LOGSNP0 is the subclass in which φ is a first-order predicate without quantifiers and x is a bounded lists of indices of input bits. LOGSNP is also the closure of LOGSNP0 under polynomial-time many-one reductions. See LOGNP and SNP for the motivation.
Defined in [PY96].
Contained in LOGNP, and therefore QPLIN.
If P = LOGSNP, then for every constructible f(n) > n, NTIME(f(n)) is contained in DTIME(g(n)sqrt(g(n))), where g(n) = O(f(n) logf(n)) [FK97].
Same as NP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines.
The Nondeterministic Time Hierarchy Theorem: If f and g are time-constructible and f(n+1)=o(g), then NTIME(f(n)) does not equal NTIME(g(n)) [SFM78] (this is actually stronger than the hierarchy theorem for DTIME).
NTIME(n) strictly contains DTIME(n) [PPS+83] (this result does not work for arbitrary f(n)).
For any constructible superpolynomial f, NTIME(f(n)) with NP oracle is not in P/poly [Kan82].
Defined by Valiant [Val03] to be "the class of physically constructible polynomial resource computers" (characterizing what "can be computed in the physical world in practice"). There he says that PhP contains P and BPP, but that it is open whether PhP contains BQP, since no scalable quantum computing proposal has been demonstrated beyond reasonable doubt.
For what it's worth, the present zookeeper has more qualms about admitting DTIME(n1000) into PhP than BQTIME(n2). It is very possible that the total number of bits or bit tranisitions that can be witnessed by any one observer in the universe is finite. (Recent observations of the cosmological constant combined with plausible fundamental physics yields a bound of 10k with k in the low hundreds.) In practice, less than 1050 bits and less than 1080 bit transitions are available for human use. (This is combining the number of atoms in the Earth with the number of signals that they can exchange in a millenium.)
The present veterinarian concurs that PhP is an unhealthy animal, although it is valid to ask whether BQP is a realistic class.
Equals DTIME(2polylog(n)).
Equals DTIME(nO(log n)).
Has the same relationship to QP that E does to EXP.
The intersection of DTIME(2n^ε) over all ε>0. (Note that the algorithm used may vary with ε.)
Defined in [Sch16] as the union of DTIME(F3(p(n))) over all elementary functions p(n), where F3 is the third level of the fast growing hierarchy, i.e., the iterated exponential function. The author describes this as the class of problems that are not in ELEMENTARY but only barely so. Unlike ELEMENTARY and PR, which have no complete problems, Tower has several natural examples of complete problems (under elementary reductions). Specifically, the Star-Free Expression Equivalence (SFEq) problem is complete for this class, as is the satisfiability of the Weak Monadic Theory of One Successor (WS1S).
Strictly contains ELEMENTARY and is strictly contained in PR.
Note that the same class is obtained if DTIME is replaced by NTIME or DSPACE in the definition.
The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following:
A fixed-parameter reduction is a Turing reduction that takes time at most f(k)p(|x|), where f is an arbitrary function and p is a polynomial. Also, if the input is (x,k), then all Weighted 3SAT instances the algorithm queries about must have the form <x',k'> where k' is at most k.
Contains FPT.
Defined in [DF99], where the following is also shown:
W[1] can be generalized to W[t].
