Editing NP (complexity) (section)

== Relationship to other classes==
{{More citations needed section|date=May 2025}}
[[Image:Complexity subsets pspace.svg|300px|thumb|right|A representation of the relation among [[Complexity class|complexity classes]]]]
[[Image:Complexity-classes-polynomial.svg|thumb|Inclusions of complexity classes including [[P (complexity)|P]], [[NP (complexity)|NP]], [[co-NP]], [[BPP (complexity)|BPP]], [[P/poly]], [[PH (complexity)|PH]], and [[PSPACE]]]]
NP contains all problems in [[P (complexity)|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 do not have to consider proofs longer than this). NP is also contained in [[EXPTIME]], since the same algorithm operates in exponential time.

co-NP contains those problems that have a simple proof for ''no'' instances, sometimes called counterexamples. For example, [[primality test]]ing 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 (this, however, is not necessarily a BPP machine<ref>{{cite web |url=https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#existsbpp |title=Complexity Zoo:E  |website=Complexity Zoo |access-date=23 March 2018 |archive-url=https://web.archive.org/web/20201111211915/https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E |archive-date=2020-11-11 |url-status=dead}}</ref>), we get the class '''MA''' solvable using an [[Arthur–Merlin protocol]] with no communication from Arthur to Merlin.

The relationship between '''[[BPP (complexity)|BPP]]''' and '''NP''' is unknown: it is not known whether '''BPP''' is a [[subset]] of '''NP''', '''NP''' is a subset of '''BPP''' or neither. If '''NP''' is contained in '''BPP''', which is considered unlikely since it would imply practical solutions for [[NP-complete]] problems, then '''NP''' = '''RP''' and '''[[PH (complexity)|PH]]''' ⊆ '''BPP'''.<ref>Lance Fortnow, [http://weblog.fortnow.com/2005/12/pulling-out-quantumness.html Pulling Out The Quantumness],  December 20, 2005</ref>

NP is a class of [[decision problem]]s; the analogous class of function problems is [[FNP (complexity)|FNP]].

The only known strict inclusions come from the [[time hierarchy theorem]] and the [[space hierarchy theorem]], and respectively they are <math>\mathsf{NP \subsetneq NEXPTIME}</math> and <math>\mathsf{NP \subsetneq EXPSPACE}</math>.