The class of decision problems whose complements belong to NP. Equivalently, negative instances admit polynomially bounded witnesses verifiable in polynomial time. A problem is co-NP-complete when it is in co-NP and every problem in co-NP has a polynomial-time reduction to it. Unsatisfiability of a propositional formula is a basic example: its complement is the NP-complete Boolean satisfiability problem.
Articles by others on the same topic
- math.stackexchange.com/questions/361422/why-isnt-np-conp "Why isn't NP = coNP?"
- stackoverflow.com/questions/17046440/whats-the-difference-between-np-and-co-np
- cs.stackexchange.com/questions/9795/is-the-open-question-np-co-np-the-same-as-p-np
- mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p