Redirected from CoNPComplete
A more formal definition: A decision problem C is CoNPcomplete if it is in CoNP and if every problem in CoNP is manyone reducible[?] to it. This means that for every CoNP 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 CoNP problems in polynomial time.
Each CoNPComplete problem is the complement of an NPcomplete problem. The two sets are either equal or disjoint. The latter is thought more likely, but this is not known. See CoNP and NPcomplete for more details.
Search Encyclopedia
