Shirt a Phobia

Sample Page

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.

The concept is of particular interest in the study of the P=NP problem, and in NP-completeness. See co-NP and NP-complete for more details.

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

The concept of co-NP-completeness is not particularly distinct from the concept of NP-completeness, since every NP problem is trivially convertible to a co-NP problem and vice-versa, by reversing “accept” and “reject”. Consequently, every NP-complete problem can be converted to a co-NP complete problem.

This does not mean, however, that the concept of co-NP-completeness is useless, since it is possible that there exists a problem that is NP but not co-NP. Reversing the labels “accept” and “reject” results in a problem that is co-NP but not NP. It is an open problem whether NP=co-NP. Since the problem of P=NP is also open, all known instances of problems in are stuck in P.

Examples

One example of a co-NP-complete problem is checking 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 complementary to the Boolean satisfiability problem, which asks whether there exists at least one such assignment, and is NP-complete.[1] In more detail:

  • Given a formula, if it is not a tautology, then it can be disproven in polynomial time by an explicit assignment.
  • Given a formula, if it is satisfiable, then it can be proven in polynomial time by an explicit assignment.

If any sparse language is co-NP-complete (or even just co-NP-hard), then P = NP.[2] This result is used in Mahaney’s theorem.[3]

References

  1. ^ a b Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.
  2. ^ Fortune, S. (1979). “A Note on Sparse Complete Sets” (PDF). SIAM Journal on Computing. 8 (3): 431–433. doi:10.1137/0208034. hdl:1813/7473.
  3. ^ Hartmanis, J.; Mahaney, S. R. (1980), Dembiński, P. (ed.), “An essay about research on sparse NP complete sets”, Mathematical Foundations of Computer Science 1980, vol. 88, Berlin/Heidelberg: Springer-Verlag, pp. 40–57, doi:10.1007/bfb0022494, ISBN 978-3-540-10027-0{{citation}}: CS1 maint: work parameter with ISBN (link)