Why is NP not trivially equal to Co-NP? (a.k.a. what does Co-NP mean exactly?) [duplicate]

Question

I've been trying to wrap my head around Co-NP, and how it's different to NP, but I am having some trouble.

Co-NP is defined by Wikipedia as this: "A decision problem $\mathcal{X}$ is a member of co-NP if and only if its complement $\overline{\mathcal{X}}$ is in the complexity class NP."

When it was explained to me in class, and after reading about it, my understanding is that if a problem $\mathcal{X}$ is defined to be the answer to $x \in L$ for some $x$ and some language $L$, and $\overline{\mathcal{X}}$ is defined to be $x \notin L$ for the same $x, L$.

Am I right? If I am, how is it different to find the answer to $\mathcal{X}$ and $\overline{\mathcal{X}}$? Knowing that $\mathcal{X}$ results to true or false would tell you that $\overline{\mathcal{X}}$ results to the opposite, wouldn't it?

Edit: I believe this question to be different enough to "Why can't we flip the answer of a NDTM efficiently?" to have merit, as the discussion is being held in a different language and approach.

Answer 1

The Definitions

This comes from the one-sidedness of the definition $NP$, that (we think) is inherent to the class.

One definition of $NP$ is the set of languages $L$ such that there is some for every $x \in L$, there exists a certificate $c$ polynomial-sized relative to $x$, and an algorithm to check if $c$ is a valid certificate that runs in polynomial time.

This definition says absolutely nothing about strings $y \not \in L$. If a word is in our language, there's some certificate. But there might not be certificates for each string not in the language.

So, if we have a magic guessing machine (aka non-determinism, the $N$ of $NP$), we can magically guess a certificate for any $x$ that is in $L$, but to show that $y$ is not in $L$, we have to iterate through all potential certificates and show that none of them are valid.

Example

This is probably made more clear with an example. Let's suppose we have some problem where we have two sets $A$ and $B$, and we want to test if $A \subseteq B$. Let's assume all members of $A$ and $B$ are polynomially sized, and there's a polynomial check to test if any given member is in $A$ or $B$, but there's potentially exponentially many elements in both $A$ and $B$.

This problem is in $co-NP$. Why? Because there's an easy certificate for the "no" case. If $A \not \subseteq B$, then we can just say "Look, I know it's not a subset, since I found this element in $A$ that's not in $B$".

But, to show that there is a subset, we have to go through all elements and show that none of them are in $A$ but not in $B$. So this problem is easy to certify in the no case, but hard in the yes-case.

Implications

Why does this matter? In practice, it tells us the direction that is easy to guess, the direction where heuristics or local search help us the most, and the direction that has the potential to be fast.

For example, consider the travelling salesman problem. Say we want a path shorter than $k$. We can use a bunch of heuristics to try to find the shortest path through all cities. If it finds one of length less than $k$, then we know the solution to the decision problem: a tour of length $k$ or less exists. If it doesn't find one, we have no extra information. There could have been some path that our heuristics missed.

$NP$ problems are ones where the "yes" instances give us this certainty, a "for-sure yes" answer. We search, and if we find one solution/certificate, we know the answer is yes. But to say no, we need to look at all certificates.

$Co-NP$ is where we are searching for a certificate that says "for-sure no", where a yes is only found by looking at all potential certificates and seeing none work.