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 ${\displaystyle O(f(n))}$. Note that some authors choose to call this class TIME.

Of great relevance to DTIME is the Time Hierarchy Theorem: For any constructible function ${\displaystyle f(n)}$ greater than ${\displaystyle n}$, DTIME(${\displaystyle f(n)}$) is strictly contained in DTIME(${\displaystyle f(n)\log(f(n))\log \log(f(n))}$) [HS65]. As a corollary, P ⊂ EXP.

For any space constructible ${\displaystyle f(n)}$, DTIME(${\displaystyle f(n)}$) is strictly contained in DSPACE(${\displaystyle f(n)}$) [HPV77].

Also, DTIME(${\displaystyle n}$) is strictly contained in NTIME(${\displaystyle n}$) [PPS+83] (this result does not work for arbitrary ${\displaystyle f(n)}$).

For any constructible superpolynomial ${\displaystyle f(n)}$, DTIME(${\displaystyle f(n)}$) with PP oracle is not in P/poly (see [All96]).

More about...

HeurNTIME_{${\displaystyle \delta }$}(f(n)): Heuristic NTIME

Defined as Heur_{${\displaystyle \delta }$}DTIME, but for non-deterministic heuristic algorithms.

NP is not contained in HeurNTIME_{${\displaystyle 1/2+1/{n^{a}}}$}(${\displaystyle n^{c}}$) for any constants ${\displaystyle a,c}$ [Per07].

More about...

LOGSNP: Logarithmically-Restricted SNP

The class of decision problems expressible in logical form as

The set of I for which there exists a subset S={s₁,...,s_{log n}} of {1,...,n} of size log n, such that for all x there exists j in S such that the predicate φ(I,s_j,x,j) holds. Here x is a logarithmic-length string, or equivalently a polynomially bounded number, and φ is computable in P.

LOGSNP₀ 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 LOGSNP₀ 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(2^O(n))).

P^NE = NP^NE [Hem89].

Contained in NEXP.

More about...

NEE: Nondeterministic EE

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

If MA_E = NEE then MA = NEXP ∩ coNEXP [IKW01].

Contained in NEEXP.

More about...

NEEXP: Nondeterministic EEXP

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

Equals MIP_EXP (unrelativized).

More about...

NEXP: Nondeterministic EXP

Nondeterministic exponential time (i.e. NTIME(2^p(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:

• If P = RP, then NEXP is not computable by polynomial-size arithmetic circuits.
• If P = BPP and if checking whether a Boolean circuit computes a function that is close to a low-degree polynomial over a finite field is in P, then NEXP is not in P/poly.
• If NEXP is in P/poly, then NEXP is in P^Perm.

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(2^O(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...