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:
“Sometimes in our relationship to another human being the proper balance of friendship is restored when we put a few grains of impropriety onto our own side of the scale.”
—Friedrich Nietzsche (1844–1900)
“Some [adolescent] girls are depressed because they have lost their warm, open relationship with their parents. They have loved and been loved by people whom they now must betray to fit into peer culture. Furthermore, they are discouraged by peers from expressing sadness at the loss of family relationships—even to say they are sad is to admit weakness and dependency.”
—Mary Pipher (20th century)
“... too much attention is paid to dress by those who have neither the excuse of ample means nor of social claims.... The injury done by this state of things to the morals and the manners of our lower classes is incalculable.”
—Mrs. H. O. Ward (1824–1899)