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
NAuxPDAp - NC - NC0 - NC1 - NC2 - NE - NE/poly - Nearly-P - NEE - NEEE - NEEXP - NEXP - NEXP/poly - NIPZK - NIQSZK - NISZK - NISZKh - NL - NL/poly - NLIN - NLO - NLOG - NMCL - NONE - NNC(f(n)) - NP - NPC - NPC - NPcc - NPcc - NPI - NP ∩ coNP - (NP ∩ coNP)/poly - NP/log - NPMV - NPMV-sel - NPMVt - NPMVt-sel - NPO - NPOPB - NP/poly - (NP,P-samplable) - NPR - NPSPACE - NPSV - NPSV-sel - NPSVt - NPSVt-sel - NQL - NQL - NQP - NSPACE(f(n)) - NT - NT* - NTIME(f(n))
naCQP: non-adaptive Collapse-free Quantum Polynomial time
Defined in the conference version of [ABFL14]. Same as PDQP.
NAuxPDAp: Nondeterministic Auxiliary Pushdown Automata
The class of problems solvable by nondeterministic logarithmic-space and polynomial-time Turing machines with auxiliary pushdown.
NC: Nick's Class
(Named in honor of Nick Pippenger.)
NCi is the class of decision problems solvable by a uniform family of Boolean circuits, with polynomial size, depth O(logi(n)), and fan-in 2.
Then NC is the union of NCi over all nonnegative i.
Also, NC equals the union of PT/WK(logkn, nk)/poly over all constants k.
NCi is contained in ACi; thus, NC = AC.
Contains NL, in fact NL is contained in NC2.
Generalizations include RNC and QNC.
[IN96] construct a candidate pseudorandom generator in NC based on the subset sum problem.
For a random oracle A, (NCi)A is strictly contained in (NCi+1)A, and uniform NCA is strictly contained in PA, with probability 1 [Mil92].
In descriptive complexity, NC can be defined by FO[]
Log space uniform NC is contained in ATIME(poly(log(n))) = polyL [RUZ81].
NC0: Level 0 of NC
By definition, a decision problem in NC0 can depend on only a constant number of bits of the input. Thus, NC0 usually refers to functions computable by constant-depth, bounded-fanin circuits.
There is a family of permutations computable by a uniform family of NC0 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 NC0, 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.
NC1: Level 1 of NC
See NC for definition.
[KV94] give a family of functions that is computable in NC1, 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 NC1 = ACC0 [BT88].
As an application of this result, NC1 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 NC1 - i.e. that NC1 is contained in 2-EQBP. (Complex amplitudes are needed for this result.)
Contains TC0.
NC1 contains the integer division problem [BCH86], even if an L-uniformity condition is imposed [CDL01].
UE*-uniform NC1 is equal to ALOGTIME [RUZ81].
NC2: Level 2 of NC
See NC for definition.
Contains AC1 and DET, both of which contain NL. It seems we currently (as of this writing, 15 Jun 2022) do not know any problem in NC2 that's not known to be in AC1∪ DET (see this question).
NE: Nondeterministic E
Nondeterministic exponential time with linear exponent (i.e. NTIME(2O(n))).
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 2n/nk 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(22O(n))).
If MAE = 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(22p(n)) for p a polynomial).
Equals MIPEXP (unrelativized).
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 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 PPerm.
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 and coSBP. There are oracles separating NIPZK from PZK, coNIPZK, and SBP [BCHTV17], [DGPV20].
[M08] showed a complete promise-problem for NIPZK, called Uniform (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. [DGPV20] showed Uniform is in coSBP.
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.
There is an oracle separating NISZK from PP [BCHTV17].
NISZKh: NISZK With Limited Help
The non-interactive analogue of SZKh.
Defined in [BG03], where the following was also shown:
- NISZKh contains NISZK and is contained in SZK.
- Graph Isomorphism is in NISZKh.
- The following problem is complete for NISZKh: Given two functions from {0,1}n to {0,1}n (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 NISZKh is not in BQP.
NL: Nondeterministic Logarithmic-Space
NL is to L as NP is to P. Not known whether a particular relation (equality or inequality) between P and NP implies the same relation between L and NL.
In a breakthrough result, was shown to equal coNL [Imm88] [Sze87]. (Though contrast to mNL.)
Is contained in LOGCFL [Sud78], as well as NC2.
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 SAC1.
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.
NMCL: Nondeterministic Moore-Crutchfield Languages
Alternative name for QRL. Named such in <ref>Abuzer Yakaryilmaz, A. C. Cem Say. Languages recognized by nondeterministic quantum finite automata. https://arxiv.org/abs/0902.2081</ref>.
Not to be confused with the similar NQL.
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
- If the answer is "yes," at least one computation path accepts.
- 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 Σ2P [BHZ87].
PH also collapses to Σ2P 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 ), 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:
- 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.
- 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 F1,...,Fk, if you can rule out even one of the 2k possibilities in polynomial time (e.g., "if F1,...,Fk-1 are all unsatisfiable then Fk is satisfiable"), then P = NP.
NPC: 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 PC = NPC, nor are implications known among this question, PR versus NPR, and P versus NP.
However, [CKK+95] show that if P/poly does not equal NP/poly then PC does not equal NPC.
[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 {nk} of positive integers, t(nk k!) grows faster than polylogarithmically in k, then PC does not equal NPC.
See also VNPk.
NPcc: Communication Complexity NP
The analogue of Pcc for nondeterministic communication complexity. Both communication bits and nondeterministic guess bits count toward the complexity.
Does not equal Pcc or coNPcc because of the EQUALITY problem. Also, does not contain BPPcc because of that problem.
Is not contained in BPPcc (first shown by [BFS86]).
SET-INTERSECTION, in which Alice's and Bob's strings are identified with characteristic vectors of sets and yes-inputs are intersecting while no-inputs are disjoint, is the canonical NPcc-complete problem. Sometimes SET-DISJOINTNESS also refers to this problem, but sometimes it refers to the complement of this problem.
The complexity measure corresponding to NPcc is equivalent to the log of the number of rectangles needed to cover exactly the set of 1-entries of the communication matrix.
NPcc: NPcc in NOF model, players
Has the same relation to NPcc and NP as Pcc does to Pcc and P.
NPcc is not contained in BPPcc for players, for any constant . As a result, NPcc is not equal to RPcc 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 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 PNP ∩ 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.
Is equal to Low(NP)={L : NPL=NP} [Sch83].
(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 S2PNP ∩ 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."
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].
NPMVt: NPMV Total
The class of all (possibly multivalued) NPMV functions that are total (that is, defined for every input).
NPMVt-sel: NPMVt Selective
Has the same relation to NPMVt 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].
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].
NPR: NP Over The Reals
An analog of NP for Turing machines over a real number field.
Defined in [BCS+97].
It is unknown whether PR = NPR, nor are implications known among this question, PC versus NPC, and P versus NP.
Also, in contrast to the case of NPC, it is an open problem to show that P/poly distinct from NP/poly implies PR distinct from NPR. 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 VNPk.
NPSPACE: Nondeterministic PSPACE
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 NPSVt.
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].
NPSVt: NPSV Total
The class of all NPSV functions that are total (that is, defined on every input).
Contained in NPMVt.
NPSVt-sel: NPSVt Selective
Has the same relation to NPSVt 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].
Unrelated to the other NQL below.
NQL: Nondeterministic Quantum Languages
An unfortunate name collision. The class of problems nondeterministically recognized by Kondacs-Watrous Quantum Finite Automata. These are automata that undergo a unitary transformation for each symbol consumed, and are measured after each step to check for acceptance or rejection. The "nondeterminism" refers to the fact that the automaton will accept with positive probability if in the language, or with exactly zero probability otherwise.
Has the same caveats as NQP and EQP because of the exact acceptance probabilities.
Initially studied in <ref>A. Kondacs; J. Watrous. On the power of quantum finite state automata. https://ieeexplore.ieee.org/document/646094</ref>, where they show that it contains all regular languages. In <ref>Abuzer Yakaryılmaz and A.C. Cem Say. Languages recognized by nondeterministic quantum finite automata. https://arxiv.org/abs/0902.2081v2</ref> it was shown that this inclusion was strict. Also showed that NQL = S≠
Contrast with QRL, which is a different model of quantum finite automaton, in which measurement only occurs at the end.
Unrelated to the other NQL above.
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)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).
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 2poly(|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].