co-NP

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 if and only if for every no-instance we have a polynomial-length "certificate" and there is a polynomial-time algorithm that can be used to verify any purported certificate.

Unsolved problem in computer science:

${\textsf {NP}}\ {\overset {?}{=}}\ {\textsf {co-NP}}$

(more unsolved problems in computer science)

That is, co-NP is the set of decision problems where there exists a polynomial $p(n)$ and a polynomial-time bounded Turing machine M such that for every instance x, x is a no-instance if and only if: for some possible certificate c of length bounded by $p(n)$ , the Turing machine M accepts the pair $(x, c)$ .[1]

Complementary Problems

While an NP problem asks whether a given instance is a yes-instance, its complement asks whether an instance is a no-instance, which means the complement is in co-NP. Any yes-instance for the original NP problem becomes a no-instance for its complement, and vice versa.

Unsatisfiability

An example of an NP-complete problem is the Boolean satisfiability problem: given a Boolean formula, is it satisfiable (is there a possible input for which the formula outputs true)? The complementary problem asks: "given a Boolean formula, is it unsatisfiable (do all possible inputs to the formula output false)?". Since this is the complement of the satisfiability problem, a certificate for a no-instance is the same as for a yes-instance from the original NP problem: a set of Boolean variable assignments which make the formula true. On the other hand, a certificate of a yes-instance for the complementary problem would be equally as complex as the no-instance of the original NP satisfiability problem.

Dual Problems

co-NP-completeness

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.

Tautology Reduction

Determining if a formula in propositional logic is a tautology is co-NP-complete: that is, if the formula evaluates to true under every possible assignment to its variables.[1]

Relationship to other classes

Inclusions of complexity classes including P, NP, co-NP, BPP, P/poly, PH, and PSPACE

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., ${\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., ${\textsf {co-NP}}\subseteq {\textsf {NP}}$ . Thus ${\textsf {co-NP}}={\textsf {NP}}$ . The proof that no co-NP-complete problem can be in NP if ${\textsf {NP}}\neq {\textsf {co-NP}}$ is symmetrical.

co-NP is a subset of PH, which itself is a subset of PSPACE.

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.

References

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 ed.). 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.

External links

Complexity Zoo: coNP

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[A&B-1] Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. p. 56. ISBN 978-0-521-42426-4.

[2] Hopcroft, John E. (2000). Introduction to Automata Theory, Languages, and Computation (2nd ed.). Boston: Addison-Wesley. ISBN 0-201-44124-1. Chap. 11.

[3] Goldreich, Oded (2010). P, NP, and NP-completeness: The Basics of Computational Complexity. Cambridge University Press. p. 155. ISBN 9781139490092.

Important complexity classes
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NL-complete NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system
List of complexity classes