Whats the difference between NP and co-NP

Question

I know their complete counterparts mean that NP - complete is the hardest in the NP problems and co-NP-complete means the hardest in co-NP problems but whats the difference between the two? My textbook said "The yes and no are reversed" which doesn't leave that much of a clue to me.

Answer 1

When you want to prove the difficulty of a problem, you have to turn it into something called a decision problem, which means a "yes/no" answer type problem. For example, in Set Cover, we may ask "can we cover all elements using only X subsets?" where X is some arbitrary number. We can show that this problem exists in NP because a solution to it is easily verifiable; you provide the X subsets, and I check to see if all elements are covered in polynomial time. If we can answer efficiently answer "yes" to the decision problem, then we can minimize X and thus solve the entire Set Cover problem efficiently (thereby proving P=NP).

Co-* (Co-NP, Co-NP-complete) focuses on answering "no" to the complemented decision problem. For example, the complemented decision problem of Set Cover would be "For every combination of X subsets, is it impossible to cover all elements?" Answering "no" to this question requires you to provide a counter-example.

In summary: NP is concerned with a "yes" answer to some decision problem. Co-NP is concerned with a "no" answer to the same, but complemented, decision problem.