Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Co-NP
Summary
In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP if and only if for every no-instance we have a polynomial-length "certificate" and there is a polynomial-time algorithm that can be used to verify any purported certificate.
That is, co-NP is the set of decision problems where there exists a polynomial p(n) and a polynomial-time bounded Turing machine M such that for every instance x, x is a no-instance if and only if: for some possible certificate c of length bounded by p(n), the Turing machine M accepts the pair (x, c).
Complement (complexity)
While an NP problem asks whether a given instance is a yes-instance, its complement asks whether an instance is a no-instance, which means the complement is in co-NP. Any yes-instance for the original NP problem becomes a no-instance for its complement, and vice versa.
An example of an NP-complete problem is the Boolean satisfiability problem: given a Boolean formula, is it satisfiable (is there a possible input for which the formula outputs true)? The complementary problem asks: "given a Boolean formula, is it unsatisfiable (do all possible inputs to the formula output false)?". Since this is the complement of the satisfiability problem, a certificate for a no-instance is the same as for a yes-instance from the original NP problem: a set of Boolean variable assignments which make the formula true. On the other hand, a certificate of a yes-instance for the complementary problem would be equally as complex as the no-instance of the original NP satisfiability problem.
Duality (optimization)
co-NP-complete
A problem L is co-NP-complete if and only if L is in co-NP and for any problem in co-NP, there exists a polynomial-time reduction from that problem to L.
Determining if a formula in propositional logic is a tautology is co-NP-complete: that is, if the formula evaluates to true under every possible assignment to its variables.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.