Co-NP-Complete

#REDIRECT Co-NP-complete

Co-NP-complete

In Computational 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 complexity classes P and NP. 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 polynomial-time many-one reduction 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 (complexity) 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. Complexity classes

See other meanings of words starting from letter:

C

CA | CB | CD | CE | CF | CG | CH | CI | CJ | CK | CL | CM | CN | CO | CP | CR | CS | CT | CU | CW | CX | CY | CZ |

Words begining with Co-NP-Complete:

Co-NP-Complete
Co-NP-complete