Class Description

NTIME(f(n)): Nondeterministic f(n)-Time

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].

Linked From

DTIME(f(n)): Deterministic f(n)-Time

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, PEXP.

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]).

More about...


HeurNTIME(f(n)): Heuristic NTIME

Defined as HeurDTIME, but for non-deterministic heuristic algorithms.

NP is not contained in HeurNTIME() for any constants [Per07].

More about...


LOGSNP: Logarithmically-Restricted SNP

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].

More about...


NE: Nondeterministic E

Nondeterministic exponential time with linear exponent (i.e. NTIME(2O(n))).

PNE = NPNE [Hem89].

Contained in NEXP.

More about...


NEE: Nondeterministic EE

Nondeterministic double-exponential time with linear exponent (i.e. NTIME(22O(n))).

If MAE = NEE then MA = NEXPcoNEXP [IKW01].

Contained in NEEXP.

More about...


NEEXP: Nondeterministic EEXP

Nondeterministic double-exponential time (i.e. NTIME(22p(n)) for p a polynomial).

Equals MIPEXP (unrelativized).

More about...


NEXP: Nondeterministic EXP

Nondeterministic exponential time (i.e. NTIME(2p(n)) for p a polynomial).

Equals MIP [BFL91] (but not relative to all oracles).

NEXP is in MIP* [IV12].

NEXP is in P/poly if and only if NEXP = MA [IKW01].

[KI02] show the following:

Does not equal NP [SFM78].

Does not equal EXP if and only if there is a sparse set in NP that is not in P.

There exists an oracle relative to which EXP = NEXP but still P does not equal NP [Dek76].

The theory of reals with addition (see EXPSPACE) is hard for NEXP [FR74].

More about...


PCP(r(n),q(n)): Probabilistically Checkable Proof

The class of decision problems such that a "yes" answer can be verified by a probabilistically checkable proof, as follows.

The verifier is a polynomial-time Turing machine with access to O(r(n)) uniformly random bits. It has random access to a proof (which might be exponentially long), but can query only O(q(n)) bits of the proof.

Then we require the following:

  1. If the answer is "yes," there exists a proof such that the verifier accepts with certainty.
  2. If the answer is "no," then for all proofs the verifier rejects with probability at least 1/2 (over the choice of the O(r(n)) random bits).

Defined in [AS98].

By definition NP = PCP(0,poly(n)).

MIP = PCP(poly(n),poly(n)).

PCP(r(n),q(n)) is contained in NTIME(2O(r(n))q(n) + poly(n)).

NP = PCP(log n, log n) [AS98].

In fact, NP = PCP(log n, 1) [ALM+98]!

On the other hand, if NP is contained in PCP(o(log n), o(log n)), then P = NP [FGL+91].

Also, even though there exists an oracle relative to which NP = EXP [Hel84], if we could show there exists an oracle relative to which PCP(log n, 1) = EXP, then we'd have proved P not equal to NP [For94].

Another weird oracle fact: since NP does not equal NEXP [SFM78], PCP(log n, log n) does not equal PCP(poly(n), poly(n)). However, there exist oracles relative to which the latter inequality is false [HCC+92].

More about...