Editing Co-NP (section)

==Relationship to other classes==
{{further|Complexity class}}
{{unsolved|computer science|{{tmath|1=\textsf{NP}\ \overset{?}{=}\ \textsf{co-NP} }} }}

[[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]]]]

[[P (complexity)|P]], the class of polynomial time solvable problems, is a subset of both NP and co-NP. P is thought to be a strict subset in both cases. Because P is closed under complementation, and NP and co-NP are complementary, it cannot be strict in one case and not strict in the other: if P equals NP, it must also equal co-NP, and vice versa.<ref>{{cite journal|title=P versus NP|first=Elvira|last=Mayordomo|author-link=Elvira Mayordomo|journal=Monografías de la Real Academia de Ciencias de Zaragoza|volume=26|pages=57–68|year=2004|url=https://dialnet.unirioja.es/servlet/articulo?codigo=2020397}}</ref>

NP and co-NP are also thought to be unequal,<ref>{{cite book | first = John E. | last = Hopcroft | title = Introduction to Automata Theory, Languages, and Computation | publisher = Addison-Wesley | location = Boston | year = 2000 | isbn = 0-201-44124-1 | edition = 2nd }} Chap. 11.</ref> and their equality would imply the collapse of the [[polynomial hierarchy]] PH to NP. If they are unequal, then no NP-complete problem can be in co-NP and no [[co-NP-complete]] problem can be in NP.<ref>{{cite book | title = P, NP, and NP-completeness: The Basics of Computational Complexity | last1 = Goldreich | first1 = Oded | publisher = [[Cambridge University Press]] | year = 2010 | page = 155 | authorlink = Oded Goldreich | isbn = 9781139490092 }}</ref> This can be shown as follows. Suppose for the sake of contradiction there exists an NP-complete problem {{mathcal|X}}  that is in co-NP. Since all problems in NP can be reduced to {{mathcal|X}}, it follows that for every problem in NP, we can construct a [[non-deterministic Turing machine]] that decides its complement in polynomial time; i.e., {{tmath|\textsf{NP} \subseteq \textsf{co-NP} }}. From this, it follows that the set of complements of the problems in NP is a subset of the set of complements of the problems in co-NP; i.e., {{tmath|\textsf{co-NP} \subseteq \textsf{NP} }}. Thus {{tmath|1=\textsf{co-NP} = \textsf{NP} }}. The proof that no co-NP-complete problem can be in NP if {{tmath|\textsf{NP} \neq \textsf{co-NP} }} is symmetrical.

co-NP is a subset of [[PH (complexity)|PH]], which itself is a subset of [[PSPACE]].

===Integer factorization===
{{main|Integer factorization}}
An example of a problem that is known to belong to both NP and co-NP (but not known to be in P) is [[Integer factorization]]: given positive integers ''m'' and ''n'', determine if ''m'' has a factor less than ''n'' and greater than one.  Membership in NP is clear; if ''m'' does have such a factor, then the factor itself is a certificate.  Membership in co-NP is also straightforward: one can just list the prime factors of ''m'', all greater or equal to ''n'', which the verifier can confirm to be valid by multiplication and the [[AKS primality test]]. It is presently not known whether there is a polynomial-time algorithm for factorization, equivalently that integer factorization is in P, and hence this example is interesting as one of the most natural problems known to be in NP and co-NP but not known to be in P.<ref>{{cite book
 | last = Aaronson | first = Scott | author-link = Scott Aaronson
 | editor1-last = Nash | editor1-first = John Forbes Jr. | editor1-link = John Forbes Nash Jr.
 | editor2-last = Rassias | editor2-first = Michael Th.
 | contribution = ''P'' ≟ ''NP''
 | doi = 10.1007/978-3-319-32162-2_1
 | isbn = 9783319321622
 | pages = 1–122
 | publisher = Springer International Publishing
 | title = Open Problems in Mathematics
 | contribution-url = https://www.scottaaronson.com/papers/pvsnp.pdf
 | year = 2016}} See Section 2.2.4 Factoring and Graph Isomorphism, pp. 19–20 of book (pp. 17–18 of linked version).</ref>