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:
“... the Wall became a magnet for citizens of every generation, class, race, and relationship to the war perhaps because it is the only great public monument that allows the anesthetized holes in the heart to fill with a truly national grief.”
—Adrienne Rich (b. 1929)
“Henry David Thoreau, who never earned much of a living or sustained a relationship with any woman that wasn’t brotherly—who lived mostly under his parents’ roof ... who advocated one day’s work and six days “off” as the weekly round and was considered a bit of a fool in his hometown ... is probably the American writer who tells us best how to live comfortably with our most constant companion, ourselves.”
—Edward Hoagland (b. 1932)
“I am ... by tradition and long study a complete snob. P. Marlowe and I do not despise the upper classes because they take baths and have money; we despise them because they are phony.”
—Raymond Chandler (1888–1959)