Encyclopedia > Co-NP-Complete

  Article Content

Co-NP-complete

Redirected from Co-NP-Complete

In complexity theory, the complexity class Co-NP-complete is the set of problems that are the hardest problems in Co-NP, in the sense that they are the ones most likely not to be in P. If you can find a way to solve a Co-NP-complete problem quickly, then you can use that algorithm to solve all Co-NP problems quickly.

A more formal definition: A decision problem C is Co-NP-complete if it is in Co-NP and if every problem in Co-NP is 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.

Each Co-NP-Complete problem is the complement of an NP-complete problem. The two sets are either equal or disjoint. The latter is thought more likely, but this is not known. See Co-NP and NP-complete for more details.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Grand Prix

... with ...

 
 
 
This page was created in 49.5 ms