Computer science Computational complexity: resources and classes Concept
co-NP
Summary
co-NP is the complexity class of decision problems whose complement lies in NP. For these problems, the "no" answers have short certificates that can be checked in polynomial time. The set of propositional tautologies is a typical member. It is an open question whether co-NP equals NP; if they differ, then P differs from NP as well.
Where this leads
2 pages build on this one.
Further reading
About this page
| Tag | 5HWR2NK8N1 |
|---|---|
| URI | m2://5HWR2NK8N1 |
| Kind | concept |
| Writing | W0 stub |
| MSC | 68Q15 |
| Same as | |
| Changed | 3 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.