Information AboutCo-np-complete |
| CATEGORIES ABOUT CO-NP-COMPLETE | |
| complexity classes | |
|
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 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. 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. 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. |
|
|