##### Wikipedia

**Co-NP**

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 $\overline{\mathcal{X}}$ is in the complexity class ** NP**. Instances of decision problems in **co-NP** are sometimes called "counterexamples". In simple terms, **co-NP** is the class of problems for which efficiently *verifiable* proofs of "no" instances exist. Equivalently, **co-NP** is the set of decision problems where the "no" instances can be *solved* in polynomial time by a theoretical non-deterministic Turing machine.

An example of an NP-complete problem is the subset sum problem: given a finite set of integers, is there a non-empty subset that sums to zero? To give a proof of a "yes" instance, one must specify a non-empty subset that does sum to zero. The complementary problem is in **co-NP** and asks: "given a finite set of integers, does every non-empty subset have a non-zero sum?".