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:
“Artists have a double relationship towards nature: they are her master and her slave at the same time. They are her slave in so far as they must work with means of this world so as to be understood; her master in so far as they subject these means to their higher goals and make them subservient to them.”
—Johann Wolfgang Von Goethe (1749–1832)
“In contrast with envy, which usually occurs between two people and is focused upon another person’s qualities or possessions, jealousy occurs when a third person becomes a threat to a dyad. Jealousy involves the loss or the impending loss of a relationship that one wants to hold onto, a relationship that is vital to personal fulfillment and claimed as one’s own.”
—Carol S. Becker (b. 1942)
“Genocide begins, however improbably, in the conviction that classes of biological distinction indisputably sanction social and political discrimination.”
—Andrea Dworkin (b. 1946)