co-NP-complete

In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP complete problem with only polynomial overhead. If P is different from co-NP, then all of the co-NP complete problems are not solvable in polynomial time. If there exists a way to solve a co-NP-complete problem quickly, then that algorithm can be used to solve all co-NP problems quickly.

Each Co-NP-complete problem is the complement of an NP-complete problem. There are some problems in both NP and co-NP, for example all problems in P or integer factorization; however, it is not known if the sets are equal, although inequality is thought more likely. See co-NP and NP-complete for more details.

Fortune showed in 1979 that if any sparse language is co-NP-complete (or even just co-NP-hard), then P = NP,^[1] a critical foundation for Mahaney's theorem.

Formal definition

A decision problem C is co-NP-complete if it is in co-NP and if every problem in co-NP is polynomial-time many-one reducible to it. This means that for every Co-NP problem L, there exists a polynomial time algorithm which can transform any instance of L into an instance of C with the same truth value. As a consequence, if we had a polynomial time algorithm for C, we could solve all co-NP problems in polynomial time.

Example

One simple example of a co-NP-complete problem is tautology, the problem of determining whether a given Boolean formula is a tautology; that is, whether every possible assignment of true/false values to variables yields a true statement. This is closely related to the Boolean satisfiability problem, which asks whether there exists at least one such assignment. Note that the tautology problem for positive Boolean formulae remains co-NP complete, even though the satisfiability problem is trivial, as every positive Boolean formula is satisfiable.

References

↑ S. Fortune. A note on sparse complete sets. SIAM Journal on Computing, volume 8, issue 3, pp.431–433. 1979.

Important complexity classes (more)

Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX

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

This article is issued from Wikipedia - version of the 7/15/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.