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 to, relationship and/or classes:
“Women, because of their colonial relationship to men, have to fight for their own independence. This fight for our own independence will lead to the growth and development of the revolutionary movement in this country. Only the independent woman can be truly effective in the larger revolutionary struggle.”
—Women’s Liberation Workshop, Students for a Democratic Society, Radical political/social activist organization. “Liberation of Women,” in New Left Notes (July 10, 1967)
“We must introduce a new balance in the relationship between the individual and the government—a balance that favors greater individual freedom and self-reliance.”
—Gerald R. Ford (b. 1913)
“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)