Co-NP-complete

In computational complexity theory, the complexity class co-NP-complete is the set of the most difficult decision problems of the class co-NP, in the sense that they are the least likely to belong to the complexity class P. If a way of solving a co-NP-complete problem in polynomial time is found, the algorithm used would serve to solve all co-NP problems with the same complexity.

More precisely, a decision problem C belongs to co-NP-complete if it is in co-NP and if every co-NP problem has a polynomial transformation to him. This means that for every L problem in co-NP, there exists an algorithm working in polynomial time that can transform an instance of L into an instance of C with the same result. Consequently, if one had an algorithm that worked in polynomial time for C, one would have an algorithm in polynomial time for each of the co-NP problems.

Each problem in co-NP-complete is the complement of one in NP-complete. The two sets are either equal or disjoint. It is the latter that is assumed to be true, but has not been proven.