Complexity Zoo:N

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

---

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

---

NAuxPDA^p - NC - NC⁰ - NC¹ - NC² - NE - NE/poly - Nearly-P - NEE - NEEE - NEEXP - NEXP - NEXP/poly - NIPZK - NIQSZK - NISZK - NISZK_h - NL - NL/poly - NLIN - NLO - NLOG - NMCL - NONE - NNC(f(n)) - NP - NPC - NP_C - NP^cc - NP_$k$^cc - NPI - NP ∩ coNP - (NP ∩ coNP)/poly - NP/log - NPMV - NPMV-sel - NPMV_t - NPMV_t-sel - NPO - NPOPB - NP/poly - (NP,P-samplable) - NP_R - NPSPACE - NPSV - NPSV-sel - NPSV_t - NPSV_t-sel - NQL - NQL - NQP - NSPACE(f(n)) - NT - NT* - NTIME(f(n))

NAuxPDA^p: Nondeterministic Auxiliary Pushdown Automata

The class of problems solvable by nondeterministic logarithmic-space and polynomial-time Turing machines with auxiliary pushdown.

Equals LOGCFL [Sud78].

---

NC: Nick's Class

(Named in honor of Nick Pippenger.)

NCⁱ is the class of decision problems solvable by a uniform family of Boolean circuits, with polynomial size, depth O(logⁱ(n)), and fan-in 2.

Then NC is the union of NCⁱ over all nonnegative i.

Also, NC equals the union of PT/WK(log^kn, n^k)/poly over all constants k.

NCⁱ is contained in ACⁱ; thus, NC = AC.

Contains NL.

Generalizations include RNC and QNC.

[IN96] construct a candidate pseudorandom generator in NC based on the subset sum problem.

For a random oracle A, (NCⁱ)^A is strictly contained in (NCⁱ⁺¹)^A, and uniform NC^A is strictly contained in P^A, with probability 1 [Mil92].

In descriptive complexity, NC can be defined by FO[$\log(n)^{O(1)}$]

---

NC⁰: Level 0 of NC

By definition, a decision problem in NC⁰ can depend on only a constant number of bits of the input. Thus, NC⁰ usually refers to functions computable by constant-depth, bounded-fanin circuits.

There is a family of permutations computable by a uniform family of NC⁰ circuits that is P-hard to invert [Has88].

Recently [AIK04] solved a longstanding open problem by showing that there exist pseudorandom generators and one-way functions in NC⁰, based on (for example) the hardness of factoring. Specifically, in these generators every bit of the output depends on only 4 input bits. Whether the dependence can be reduced to 3 bits under the same cryptographic assumptions is open, but [AIK04] have some partial results in this direction. It is known that the dependence cannot be reduced to 2 bits.

---

NC¹: Level 1 of NC

See NC for definition.

[KV94] give a family of functions that is computable in NC¹, but not efficiently learnable unless there exists an efficient algorithm for factoring Blum integers.

Was shown to equal 5-PBP [Bar89]. On the other hand, width 5 is necessary unless NC¹ = ACC⁰ [BT88].

As an application of this result, NC¹ can be simulated on a quantum computer with three qubits, one initialized to a pure state and the remaining two in the maximally mixed state [ASV00]. Surprisingly, [AMP02] showed that only a single qubit is needed to simulate NC¹ - i.e. that NC¹ is contained in 2-EQBP. (Complex amplitudes are needed for this result.)

Is contained in L [Bor77].

Contains TC⁰.

NC¹ contains the integer division problem [BCH86], even if an L-uniformity condition is imposed [CDL01].

U_E^*-uniform NC¹ is equal to ALOGTIME [RUZ81].

---

NC²: Level 2 of NC

See NC for definition.

Contains NL.

---

NE: Nondeterministic E

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

P^NE = NP^NE [Hem89].

Contained in NEXP.

---

Nearly-P: Languages Superpolynomially Close to P

The set of languages L such that for every k, there is a language L_k in P that differs from L on at most 2ⁿ/n^k inputs of length n. Discussed in [NS05] and implicitly defined in [Yam99].

---

NE/poly: Nonuniform NE

Contains coNE, just as NEXP/poly contains coNEXP.

---

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.

---

NEEE: Nondeterministic EEE

Nondeterministic triple-exponential time with linear exponent.

---

NEEXP: Nondeterministic EEXP

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

Equals MIP_EXP (unrelativized).

---

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 matrix permanent is NEXP-complete.

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

---

NEXP/poly: Nonuniform NEXP

Contains coNEXP (folklore result reported in Fortnow's weblog).

---

NIPZK: Non-Interactive PZK

Defined in [M08] based on [DDPY98],[BFM88].

Contained in PZK.

[M08] showed a complete promise-problem for NIPZK, called Unifrom (UN). Instances in UN are circuits with n+1 output bits. The first n bits represent the uniform distribution, and the last bit is 1 with probability at least 2/3. For instances not in UN, when the last bit is 1, at most 1/3 of the strings of length n can appear as the output of the circuit. The problem is to decide which is the case.

---

NIQSZK: Non-Interactive QSZK

Has the same relation to QSZK as NISZK does to SZK.

Defined in [Kob02], where it was also shown that the following promise problem is complete for NIQSZK. Given a quantum circuit, we are promised that the state it prepares (when run on the all-0 state, and tracing out non-output qubits) has trace distance either at most 1/3 or at least 2/3 from the maximally mixed state. The problem is to output "no" in the former case and "yes" in the latter.

NIQPZK can be defined similarly.

---

NISZK: Non-Interactive SZK

Defined in [DDP+98].

Contained in SZK.

[GSV99] showed the following:

• If SZK does not equal BPP then NISZK does not equal BPP.
• NISZK equals SZK if and only if NISZK is closed under complement.
• NISZK has natural complete promise problems:
• Statistical Distance from Uniform (SDU): Given a circuit, consider the distribution over outputs when the circuit is given a uniformly random n-bit string. We're promised that the trace distance between this distribution and the uniform distribution is either at most 1/3 or at least 2/3. The problem is to output "yes" in the former case and "no" in the latter.
• Entropy Approximation (EA): Now we're promised that the entropy of the circuit's output distribution is either at least k+1 or at most k-1. The problem is to output "yes" in the former case and "no" in the latter.

NIPZK can be defined similarly.

---

NISZK_h: NISZK With Limited Help

The non-interactive analogue of SZK_h.

Defined in [BG03], where the following was also shown:

• NISZK_h contains NISZK and is contained in SZK.
• Graph Isomorphism is in NISZK_h.
• The following problem is complete for NISZK_h: Given two functions from {0,1}ⁿ to {0,1}ⁿ (specified by circuits), decide whether their ranges are almost equal or almost disjoint, given that one of these is the case.

The quantum lower bound for the set comparison problem in [Aar02] implies an oracle relative to which NISZK_h is not in BQP.

---

NL: Nondeterministic Logarithmic-Space

Has the same relation to L as NP does to P.

In a breakthrough result, was shown to equal coNL [Imm88] [Sze87]. (Though contrast to mNL.)

Is contained in LOGCFL [Sud78], as well as NC².

Is contained in UL/poly [RA00].

Deciding whether a bipartite graph has a perfect matching is hard for NL [KUW86].

NL can be defined in a logical formalism as SO(krom) and also as FO(tc), reachability in directed graph is NL-Complete under FO-reduction.

---

NL/poly: Nonuniform NL

Has the same relation to NL as P/poly does to P.

Is contained in ⊕L/poly [GW96], as well as SAC¹.

Equals UL/poly [RA00].

---

NLO: NL Optimization Problems

The class of optimization problems which can be solved in nondeterministic logspace.

Defined in [TAN07] as the logspace equivalent of NPO, where it is shown that the various logspace approximation classes form a hierarchy iff L ≠ NL.

As with the definition of NPO in [ACG+99], NLO is defined as a class of "structured" problems, comprising both a "solution relation" (indicating which solutions are acceptable for a given input) and a "measure function" (computing the value of each solution). The equivalent "unstructured" class is OptL. See [TAN07] for discussion.

---

NLOG: NL With Nondeterministic Oracle Tape

Same as NL -- but if there's an oracle, then NLOG can make queries nondeterministically on a polynomial-size, one-way oracle tape. (NL, by contrast, can use nondeterministic transitions only on the worktape; oracle queries have to be deterministic.)

See [LL76] or [HCK+88] for more information.

Although NLOG is contained in P, there exists an oracle relative to which that is not the case. This illustrates that care is needed when defining oracle access mechanisms.

---

NLIN: Nondeterministic LIN

Has the same relation to LIN as NP does to P.

---

NLT: Nearly Linear Time

Class of functions computable in nearly linear time n(log n)^O(1) on deterministic random access machines.

Defined in [GS89].

See also QL.

---

NNC(f(n)): NC with O(f(n)) nondeterministic gates

Same as NC, but with O(f(n)) nondeterministic gates. A nondeterministic gate has no inputs and a single output bit.

Defined in [Wol94], where the author proves various inclusions, including but not limited to NNC(poly(n))=NP, NNC(log(n))=NC, and NNC(polylog)⊆DSPACE(polylog).

---

NNLT: Nondeterministic Nearly Linear Time

Class of functions computable in nearly linear time n(log n)^O(1) on nondeterministic random access machines. Equals NQL [GS89].

Defined in [GS89].

---

NONE: The Empty Class

The class that does not contain any languages. (It might not surprise you that I put this one in at the suggestion of a mathematician...)

Is the opposite of ALL, but does not equal the complement coALL = ALL.

Is closed under polynomial-time Turing reductions :-).

Equals SPARSE ∩ coSPARSE and TALLY ∩ coTALLY.

---

NP: Nondeterministic Polynomial-Time

The class of dashed hopes and idle dreams.

More formally: an "NP machine" is a nondeterministic polynomial-time Turing machine.

Then NP is the class of decision problems solvable by an NP machine such that

1. If the answer is "yes," at least one computation path accepts.
2. If the answer is "no," all computation paths reject.

Equivalently, NP is the class of decision problems such that, if the answer is "yes," then there is a proof of this fact, of length polynomial in the size of the input, that can be verified in P (i.e. by a deterministic polynomial-time algorithm). On the other hand, if the answer is "no," then the algorithm must declare invalid any purported proof that the answer is "yes."

For example, the SAT problem is to decide whether a given Boolean formula has any satisfying truth assignments. SAT is in NP, since a "yes" answer can be proved by just exhibiting a satisfying assignment.

A decision problem is NP-complete if (1) it is in NP, and (2) any problem in NP can be reduced to it (under some notion of reduction). The class of NP-complete problems is sometimes called NPC.

That NP-complete problems exist is immediate from the definition. The seminal result of Cook [Coo71], Karp [Kar72], and Levin [Lev73] is that many natural problems (that have nothing to do with Turing machines) are NP-complete.

The first such problem to be shown NP-complete was SAT [Coo71]. Other classic NP-complete problems include:

• 3-Colorability: Given a graph, can each vertex be colored red, green, or blue so that no two neighboring vertices have the same color?
• Hamiltonian Cycle: Given a graph, is there a cycle that visits each vertex exactly once?
• Traveling Salesperson: Given a set of n cities, and the distance between each pair of cities, is there a route that visits each city exactly once before returning to the starting city, and has length at most T?
• Maximum Clique: Given a graph, are there k vertices all of which are neighbors of each other?
• Subset Sum: Given a collection of integers, is there a subset of the integers that sums to exactly x?

For many, many more NP-complete problems, see [GJ79].

NP contains P. I've discovered a marvelous proof that NP and P are unequal, but this web page is too small to contain it. Too bad, since otherwise I'd be eligible for $1,000,000 [CMI00].

There exists an oracle relative to which P and NP are unequal [BGS75]. Indeed, P and NP are unequal relative to a random oracle with probability 1 [BG81] (see [AFM01] for a novel take on this result). Though random oracle results are not always indicative about the unrelativized case [CCG+94].

There even exists an oracle relative to which the P versus NP problem is outside the usual axioms of set theory [HH76].

If we restrict to monotone classes, mP is strictly contained in mNP [Raz85].

Perhaps the most important insight anyone has had into P versus NP is to be found in [RR97]. There the authors show that no 'natural proof' can separate P from NP (or more precisely, place NP outside of P/poly), unless secure pseudorandom generators do not exist. A proof is 'natural' if it satisfies two conditions called constructivity and largeness; essentially all lower bound techniques known to date satisfy these conditions. To obtain unnatural proof techniques, some people suspect we need to relate P versus NP to heavy-duty 'traditional' mathematics, for instance algebraic geometry. See [MS02] (and the survey article [Reg02]) for a development of this point of view.

For more on P versus NP (circa 1992) see [Sip92]. For an opinion poll, see [Gas02].

If P equals NP, then NP equals its complement coNP. Whether NP equals coNP is also open. NP and coNP can be extended to the polynomial hierarchy PH.

The set of decision problems in NP, but not in P or NPC, is sometimes called NPI. If P does not equal NP then NPI is nonempty [Lad75].

Probabilistic generalizations of NP include MA and AM. If NP is in coAM (or BPP) then PH collapses to Σ₂P [BHZ87].

PH also collapses to Σ₂P if NP is in P/poly [KL82].

There exist oracles relative to which NP is not in BQP [BBB+97].

An alternate characterization is NP = PCP(log n, O(1)) [ALM+98].

Also, [Fag74] showed that NP is precisely the class of decision problems reducible to a graph-theoretic property expressible in second-order existential logic. This leads to the subclass SNP.

It is known that if any NP-complete language is sparse (contains no more than a polynomial number of strings of length $n$), then P = NP. [BH08] improved this result, showing that if any language in NP has an NP-hard set of subexponential density, then coNP is contained in NP/poly and thus, by [Yap82], PH collapses to the third level.

NP is equal to SO-E, the second-order queries where the second-order quantifiers are only existantials.

---

NPC: NP-Complete

The class of decision problems such that (1) they're in NP and (2) every problem in NP is reducible to them (under some notion of reduction). In other words, the hardest problems in NP.

Two notions of reduction from problem A to problem B are usually considered:

1. Karp or many-one reductions. Here a polynomial-time algorithm is given as input an instance of problem A, and must produce as output an instance of problem B.
2. Turing reductions, in this context also called Cook reductions. Here the algorithm for problem B can make arbitrarily many calls to an oracle for problem A.

Some examples of NP-complete problems are discussed under the entry for NP.

The classic reference on NPC is [GJ79].

Unless P = NP, NPC does not contain any sparse problems: that is, problems such that the number of 'yes' instances of size n is upper-bounded by a polynomial in n [Mah82].

A famous conjecture [BH77] asserts that all NP-complete problems are polynomial-time isomorphic -- i.e. between any two problems, there is a one-to-one and onto Karp reduction. If that's true, the NP-complete problems could be interpreted as mere "relabelings" of one another.

NP-complete problems are p-superterse unless P = NP [BKS95]. This means that, given k Boolean formulas F₁,...,F_k, if you can rule out even one of the 2^k possibilities in polynomial time (e.g., "if F₁,...,F_k-1 are all unsatisfiable then F_k is satisfiable"), then P = NP.

---

NP_C: NP Over The Complex Numbers

An analog of NP for Turing machines over a complex number field.

Defined in [BCS+97].

It is unknown whether P_C = NP_C, nor are implications known among this question, P_R versus NP_R, and P versus NP.

However, [CKK+95] show that if P/poly does not equal NP/poly then P_C does not equal NP_C.

[BCS+97] show the following striking result. For a positive integer n, let t(n) denote the minimum number of additions, subtractions, and multiplications needed to construct n, starting from 1. If for every sequence {n_k} of positive integers, t(n_k k!) grows faster than polylogarithmically in k, then P_C does not equal NP_C.

See also VNP_k.

---

NP^cc: Communication Complexity NP

The analogue of P^cc for nondeterministic communication complexity. Both communication bits and nondeterministic guess bits count toward the complexity.

Does not equal P^cc or coNP^cc because of the EQUALITY problem. Also, does not contain BPP^cc because of that problem.

Defined in [BFS86].

Contained in PH^cc.

The complexity measure corresponding to NP^cc is equivalent to the log of the number of rectangles needed to cover exactly the set of 1-entries of the communication matrix.

---

NP_$k$^cc: NP^cc in NOF model, $k$ players

Has the same relation to NP^cc and NP as P_$k$^cc does to P^cc and P.

NP_$k$^cc is not contained in BPP_$k$^cc for $k\leq (1-\delta )\cdot \log n$ players, for any constant $\delta >0$. As a result, NP_$k$^cc is not equal to RP_$k$^cc under the same conditions [DP08].

---

NPI: NP-Intermediate

Sometimes used to denote the set of decision problems in NP that are neither NP-complete (that is, in NPC) nor in P.

Is thought to contain (for example) decision versions of factoring and graph isomorphism.

Is nonempty if P does not equal NP [Lad75]. Indeed, under this assumption, it contains an infinite number of distinct polynomial-time equivalence classes.

---

NP ∩ coNP

The class of problems in both NP and coNP.

Contains factoring [Pra75].

Contains graph isomorphism under the assumption that some language in NE ∩ coNE requires nondeterministic circuits of size 2^Ω(n) ([MV99], improving [KM99]). (A nondeterministic circuit C has two inputs, x and y, and accepts on x if there exists a y such that C(x,y)=1.)

Equals P^{NP ∩ coNP} [Bra79]. In particular, if a problem in NP ∩ coNP is NP-hard with Turing reduction, then NP = coNP.

Is not believed to contain complete problems.

---

(NP ∩ coNP)/poly: Nonuniform NP ∩ coNP

Together with NP/poly ∩ coNP/poly, has the same relation to NP ∩ coNP as P/poly has to P. A language in (NP ∩ coNP)/poly is defined by a single language in NP ∩ coNP which is then modified by advice. A language in NP/poly ∩ coNP/poly comes from two possibly different languages in NP and coNP which become the same with good advice.

There is an oracle relative to which NP/poly ∩ coNP/poly, indeed NP/1 ∩ coNP/1, is not contained in (NP ∩ coNP)/poly [FFK+93]. Recently they improved this to NP/1 ∩ coNP [FF..].

If NP is contained in (NP ∩ coNP)/poly, then PH collapses to S₂P^{NP ∩ coNP} [CCH+01].

---

NP/log: NP With Logarithmic Advice

Same as NP/poly, except that now the advice string is logarithmic-size.

Shown in [FK05] that EXP ⊆ NP/log if and only if EXP = P^||NP.

---

NPMV: NP Multiple Value

The class of all (possibly partial, possibly multivalued) functions computed by an NP machine as follows: ignore the rejecting paths, and consider any output of an accepting path to be "one of the outputs."

Contains NPSV and NPMV_t.

Defined in [BLS84].

Contrast with FNP.

---

NPMV-sel: NPMV Selective

Has the same relation to NPMV as P-Sel does to P.

Defined in [HHN+95].

---

NPMV_t: NPMV Total

The class of all (possibly multivalued) NPMV functions that are total (that is, defined for every input).

---

NPMV_t-sel: NPMV_t Selective

Has the same relation to NPMV_t as P-Sel does to P.

Defined in [HHN+95].

---

NPO: NP Optimization

The class of function problems of the form, "Find any n-bit string x that maximizes a cost function C(x), where C is computable in FP (i.e. polynomial-time)."

Defined in [ACG+99].

Contains APX and NPOPB.

---

NPOPB: NPO Polynomially Bounded

The subclass of NPO problems for which the cost function is guaranteed always to be bounded by a polynomial in n (the input size).

See [ACG+99].

NPOPB equals the closure of MaxPB under PTAS reductions [CKS+99].

---

NP/poly: Nonuniform NP

Has the same relation to NP as P/poly does to P.

Contains AM. On the other hand, if NP/poly contains coNP then PH collapses to the third level.

NP/poly-natural proofs cannot show that circuit families are outside P/poly, under a pseudorandomness assumption [Rud97].

---

(NP,P-samplable): Average NP With Samplable Distributions

See AvgP for basic notions of average-case complexity.

(NP,P-samplable) is the same as DistNP, except that the distribution μ only needs to be samplable in polynomial time. μ's cumulative density function does not need to be computable in polynomial time.

Any problem complete for DistNP is also complete for (NP,P-samplable) [IL90].

---

NP_R: NP Over The Reals

An analog of NP for Turing machines over a real number field.

Defined in [BCS+97].

It is unknown whether P_R = NP_R, nor are implications known among this question, P_C versus NP_C, and P versus NP.

Also, in contrast to the case of NP_C, it is an open problem to show that P/poly distinct from NP/poly implies P_R distinct from NP_R. The difference is that in the real case, a comparison (or greater-than) operator is available, and it is not known how much power this yields in comparison to the complex case.

See also VNP_k.

---

NPSPACE: Nondeterministic PSPACE

Equals PSPACE [Sav70].

On the other hand, this result does not relativize if we allow strings of unbounded length to be written to the oracle tape. In particular, there exists an oracle relative to which NPSPACE is not contained in EXP [GTW+91].

---

NPSV: NP Single Value

The class of NPMV functions that are single-valued (i.e., such that every accepting path outputs the same value).

Defined in [BLS84].

Contains NPSV_t.

P = NP if and only if FP = NPSV.

---

NPSV-sel: NPSV Selective

Has the same relation to NPSV as P-Sel does to P.

Defined in [HHN+95].

---

NPSV_t: NPSV Total

The class of all NPSV functions that are total (that is, defined on every input).

Contained in NPMV_t.

---

NPSV_t-sel: NPSV_t Selective

Has the same relation to NPSV_t as P-Sel does to P.

Also known as NP-sel.

Defined in [HHN+95].

---

NQL: Nondet Quasi-Linear

The class of problems that can be decided in quasi-linear time by a multitape nondeterministic Turing machine. Quasi-linear here means n(log n)^k + k, for some k.

Equals NNLT.

SAT is NQL-complete under quasi-linear-time reductions (which can be computed in deterministic quasi-linear time) [Sch78].

Defined in [Sch78].

See also: NLT, Q, QL.

---

NQP: Nondeterministic Quantum Polynomial-Time

The class of decision problems solvable by a QTM in polynomial time such that a particular '|Accept>' state has nonzero amplitude at the end of the computation, if and only if the answer is 'yes.' Since it has an exact amplitude condition, NQP has the same technical caveats as EQP. Or it would, except that it turns out to equal coC₌P [FGH+98].

Defined in [ADH97].

Contrast with QMA.

---

NSPACE(f(n)): Nondeterministic f(n)-Space

Same as NPSPACE, but with f(n)-space (for some constructible function f) rather than polynomial-space machines.

Contained in DSPACE(f(n)²) [Sav70], and indeed RevSPACE(f(n)²) 95|[CP95].

NSPACE(n^k) is strictly contained in NSPACE(n^k+ε) for ε>0 [Iba72] (actually the hierarchy theorem is stronger than this, but pretty technical to state).

---

NT: Near-Testable

The class of decision problems such that whether the answer on input x agrees with the answer on input x-1 (that is, the lexicographic predecessor of x) is solvable in polynomial time. The Turing machine has to decide agreement or disagreement without access to the answer for x-1.

Is contained in E, NT*, and ⊕P. Defined in [GHJ+91] to study ⊕P-complete problems. They show that P, NT, NT*, and ⊕P are either all equal or strictly nested. In particular, they differ with probability 1 relative to a random oracle.

---

NT*: Near-Testable With Forest Ordering

Defined like NT, but with a more general ordering on inputs. A problem L is in NT* if, first, there is a partially defined predecessor function pred(x) in FP that organizes the space of inputs into a forest. The size of the lineage of each x must also be bounded by 2^poly(|x|). Second, if L(x) is the Boolean answer to L on input x, then L(x)+L(pred(x)) is computable in polynomial time; or if pred(x) does not exist, L(x) is computable in polynomial time.

Defined in [GHJ+91].

Contains NT and is contained in ⊕P. The inclusions are either both strict or both equalities (whence ⊕P = P as well).

---

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