Relationship To Other Classes
NP contains all problems in P, since one can verify any instance of the problem by simply ignoring the proof and solving it. NP is contained in PSPACE—to show this, it suffices to construct a PSPACE machine that loops over all proof strings and feeds each one to a polynomial-time verifier. Since a polynomial-time machine can only read polynomially many bits, it cannot use more than polynomial space, nor can it read a proof string occupying more than polynomial space (so we don't have to consider proofs longer than this). NP is also contained in EXPTIME, since the same algorithm operates in exponential time.
The complement of NP, co-NP, contains those problems which have a simple proof for no instances, sometimes called counterexamples. For example, primality testing trivially lies in co-NP, since one can refute the primality of an integer by merely supplying a nontrivial factor. NP and co-NP together form the first level in the polynomial hierarchy, higher only than P.
NP is defined using only deterministic machines. If we permit the verifier to be probabilistic (specifically, a BPP machine), we get the class MA solvable using a Arthur-Merlin protocol with no communication from Merlin to Arthur.
NP is a class of decision problems; the analogous class of function problems is FNP.
Read more about this topic: NP (complexity)
Famous quotes containing the words relationship and/or classes:
“If the relationship of father to son could really be reduced to biology, the whole earth would blaze with the glory of fathers and sons.”
—James Baldwin (1924–1987)
“There are four classes of idols which beset men’s minds. To these for distinction’s sake I have assigned names—calling the first class Idols of the Tribe; the second, Idols of the Cave; the third, Idols of the Market-Place; the fourth, Idols of the Theatre.”
—Francis Bacon (1561–1626)