co-NP (source code)
= co-NP
{c}
{title2=$\mathrm{coNP}=\{L:\overline L\in\mathrm{NP}\}$}
= coNP
{c}
{synonym}
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>.
Back to article page
