co-NP
Sign in to saveAlso known as coNP
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.
Wikidata facts
- Instance of
- complexity class
- Subclass of
- computational problem
- Has part
- co-NP-complete
Sources (1)
via Wikidata · CC0
~5 min read
Encyclopedic overview
8 sectionsContents
- Complementary problems
- Unsatisfiability
- co-NP-completeness
- Tautology reduction
- Relationship to other classes
- Integer factorization
- References
- External links
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 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 , the Turing machine M accepts the pair .
Excerpted from Wikipedia’s “co-NP” article, available under the CC BY-SA 4.0 licence.