Can be defined as the class of problems polynomial-time Turing reducible to the Graph Isomorphism problem.
Contains GA and is contained in Δ2P.
The Graph Isomorphism problem itself (as opposed to the set of problems Turing reducible to Graph Isomorphism) is contained in NP as well as coAM (and indeed SZK). So in particular, if Graph Isomorphism is NP-complete, then PH collapses.
Many natural problems are GI-complete (polynomial-time Turing equivalent to GI); for a partial list see the Wikipedia page. While many of these are GI for a restricted class of graphs, some surprising GI-complete problems are: isomorphism of finite automata, isomorphism of commutative class 3 nilpotent semigroups, isomorphism of algebras over a field whose radical squares to zero and whose radical quotient is abelian [Gri83], and isomorphism of context-free grammars (for all of these and further references see [ZKT85]). Conjugacy of semisimple Lie algebras given by matrices is also GI-hard, and is even GI-complete assuming one can compute relevant eigenvalues [Gro12].
See [KST93] for much more information about GI.
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
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:
For many, many more NP-complete problems, see [GJ79].
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]. P vs NP is a "Millenium Prize" problem [CMI00].
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.
The class of decision problems for which a "yes" answer can be verified by a statistical zero-knowledge proof protocol. In such an interactive proof(see IP), we have a probabilistic polynomial-time verifier, and a prover who has unbounded computational resources. By exchanging messages with the prover, the verifier must become convinced (with high probability) that the answer is "yes," without learning anything else about the problem (statistically).
What does that mean? For each choice of random coins, the verifier has a "view" of his entire interaction with prover, consisting of his random coins as well as all messages sent back and forth. Then the distribution over views resulting from interaction with the prover has to be statistically close to a distribution that the verifier could generate himself (in polynomial-time), without interacting with anyone. (Here "statistically close" means that, say, the trace distance is at most 1/10.)
The most famous example of such a protocol is for graph nonisomorphism. Given two graphs G and H, the verifier picks at random one of the graphs (each with probability 1/2), permutes its vertices randomly, sends the resulting graph to the prover, and asks, "Which graph did I start with, G or H?" If G and H are non-isomorphic, the prover can always answer correctly (since he can use exponential time), but if they're isomorphic, he can answer correctly with probability at most 1/2. Thus, if the prover always gives the correct answer, then the verifier becomes convinced the graphs are not isomorphic. On the other hand, the verifier already knew which graph (G or H) he started with, so he could simulate his entire view of the interaction himself, without the prover's help.
If that sounds like a complicated definition, well, it is. But it turns out that SZK has extremely nice properties. [Oka96] showed that:
Subsequently, [SV97] showed that SZK has a natural complete promise problem, called Statistical Difference (SD). Given two polynomial-size circuits, C0 and C1, let D0 and D1 be the distributions over their respective outputs when they're given as input a uniformly random n-bit string. We're promised that D0 and D1 have trace distance either at most 1/3 or at least 2/3; the problem is to decide which is the case.
Note: The constants 1/3 and 2/3 can be amplified to 2-poly(n) and 1-2-poly(n) respectively. But it is crucial that (2/3)2 > 1/3.
Another complete promise problem for SZK is Entropy Difference (ED) [GV99]. Here we're promised that either H(D0)>H(D1)+1 or H(D1)>H(D0)+1, where the distributions D0 and D1 are as above, and H denotes Shannon entropy. The problem is to determine which is the case.
If any hard-on-average language is in SZK, then one-way functions exist [Ost91].
See general zero-knowledge (ZK).
Contains PZK and NISZK, and is contained in AM ∩ coAM, as well as CZK and QSZK.
There exists an oracle relative to which SZK is not in BQP [Aar02].
The class of problems that are polynomial-time Turing reducible to Tensor Isomorphism. Defined in [GQ19]. Can depend on the field, and the relationship for TI over different fields is an open question, but many reductions hold for TI over any field (over finite fields or the rationals this can be done in the usual model of Turing machines; over arbitrary fields one can use the BSS model to formalize this).
Over any field F, contains GI. As with Graph Isomorphism, the Tensor Isomorphism problem itself (say, over finite fields) is contained in NP as well as coAM (and indeed SZK; the same results hold over arbitrary fields in the BSS model). So in particular, if Tensor Isomorphism is NP-complete, then PH collapses.
Many natural problems are TI-complete, such as isomorphism of d-tensors for any fixed d ≥ 3, isomorphism of algebras, conjugacy of spaces of matrices, (pseudo-)isometry of alternating matrix spaces, isomorphism of matrix p-groups of class 2 and exponent p, and equivalence of cubic forms [GQ19]. This was extended to include p-groups of class c<p and exponent p [GQ21]. Analogous classes were also defined under other group actions such as unitary, orthogonal, and symplectic groups [CGQ+24].
