Co-NP: Difference between revisions
→top: the formulation seems redundant to me, with "certificate" and "verify" being sufficient. Perhaps it was meant to be extra-helpful, but I first understood it as denying the possibility of yes-instance having yes-certificates, which is false, so it seems confusing more than helpful to me. |
|||
| Line 1: | Line 1: | ||
{{lowercase}} |
{{lowercase}} |
||
{{unsolved|computer science|{{tmath|1=\textsf{NP}\ \overset{?}{=}\ \textsf{co-NP} }} }} |
{{unsolved|computer science|{{tmath|1=\textsf{NP}\ \overset{?}{=}\ \textsf{co-NP} }} }} |
||
In [[computational complexity theory]], '''co-NP''' is a [[complexity class]]. A [[decision problem]] {{mathcal|X}} is a member of co-NP if and only if its [[complement (complexity)|complement]] {{overline|{{mathcal|X}}}} is in the complexity class [[NP (complexity)|NP]]. The class can be defined as follows: a decision problem is in co-NP precisely if for any ''no''-instance ''x'' there is a "[[Certificate (complexity)|certificate]]" which a polynomial-time algorithm can use to verify that ''x'' is a ''no''-instance |
In [[computational complexity theory]], '''co-NP''' is a [[complexity class]]. A [[decision problem]] {{mathcal|X}} is a member of co-NP if and only if its [[complement (complexity)|complement]] {{overline|{{mathcal|X}}}} is in the complexity class [[NP (complexity)|NP]]. The class can be defined as follows: a decision problem is in co-NP precisely if for any ''no''-instance ''x'' there is a "[[Certificate (complexity)|certificate]]" which a polynomial-time algorithm can use to verify that ''x'' is a ''no''-instance. |
||
Equivalently, co-NP is the set of decision problems where there exists a polynomial ''p(n)'' and a polynomial-time bounded [[non-deterministic Turing machine]] such that for every instance ''x'', ''x'' is a yes instance if and only if: for every possible certificate ''c'' of length bounded by ''p(n)'', the Turing machine accepts the pair (''x'', ''c'').<ref name="A&B">{{cite book |last1= Arora |first1= Sanjeev |last2= Barak |first2= Boaz |url= http://www.cs.princeton.edu/theory/complexity/ |title= Complexity Theory: A Modern Approach |publisher= Cambridge University Press |date= 2009 |isbn= 978-0-521-42426-4 |page=56 }}</ref> |
Equivalently, co-NP is the set of decision problems where there exists a polynomial ''p(n)'' and a polynomial-time bounded [[non-deterministic Turing machine]] such that for every instance ''x'', ''x'' is a yes instance if and only if: for every possible certificate ''c'' of length bounded by ''p(n)'', the Turing machine accepts the pair (''x'', ''c'').<ref name="A&B">{{cite book |last1= Arora |first1= Sanjeev |last2= Barak |first2= Boaz |url= http://www.cs.princeton.edu/theory/complexity/ |title= Complexity Theory: A Modern Approach |publisher= Cambridge University Press |date= 2009 |isbn= 978-0-521-42426-4 |page=56 }}</ref> |
||
Revision as of 19:28, 12 December 2020
In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement X is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely if for any no-instance x there is a "certificate" which a polynomial-time algorithm can use to verify that x is a no-instance.
Equivalently, co-NP is the set of decision problems where there exists a polynomial p(n) and a polynomial-time bounded non-deterministic Turing machine such that for every instance x, x is a yes instance if and only if: for every possible certificate c of length bounded by p(n), the Turing machine accepts the pair (x, c).[1]
Problems
The complement of any problem in NP is a problem in co-NP. An example of an NP-complete problem is the circuit satisfiability problem: given a Boolean circuit, is there a possible input for which the circuit outputs true? The complementary problem asks: "given a Boolean circuit, do all possible inputs to the circuit output false?". This is in co-NP because a polynomial-time certificate of a no-instance is a set of inputs which make the output true.
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.[citation needed]
A problem L is co-NP-complete if and only if L is in co-NP and for any problem in co-NP, there exists a polynomial-time reduction from that problem to L. An example of such problem is that of determining if a formula in propositional logic is a tautology: that is, if the formula evaluates to true under every possible assignment to its variables.[1]
Relationship to other classes
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 (and demonstrably cannot be strict in one case and not strict in the other).
NP and co-NP are also thought to be unequal.[2] If so, then no NP-complete problem can be in co-NP and no co-NP-complete problem can be in NP.[3] This can be shown as follows. Suppose for the sake of contradiction there exists an NP-complete problem X that is in co-NP. Since all problems in NP can be reduced to 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., NP ⊆ 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., co-NP ⊆ NP. Thus co-NP = NP. The proof that no co-NP-complete problem can be in NP if NP ≠ co-NP is symmetrical.
References
- ^ a b Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. p. 56. ISBN 978-0-521-42426-4.
- ^ Hopcroft, John E. (2000). Introduction to Automata Theory, Languages, and Computation (2nd Edition). Boston: Addison-Wesley. ISBN 0-201-44124-1. Chap. 11.
- ^ Goldreich, Oded (2010). P, NP, and NP-completeness: The Basics of Computational Complexity. Cambridge University Press. p. 155. ISBN 9781139490092.