2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Your question shows that you don't yet know what the class NP is. You need to be much more clear about what you're trying to say when you write "if a problem X is defined to be the answer $x \in L$ for some $x$ and some language L." This simply isn't a definition of the class NP. The two most commonly used definitions are based on either a non deterministic Turing machine or on a certificate that can be verified in polynomial time. The certificate definition is usually easier for students to work with. $\endgroup$ – Brian Borchers May 7 '15 at 4:34
  • $\begingroup$ I did not mean that to represent the definition of NP, which I'm almost sure I understand. I have read both definitions you speak of before. In that paragraph, I tried to explain what I understand to be the complement of a decision problem, in case the fault in my reasoning lies there. $\endgroup$ – diegovb May 7 '15 at 4:39
  • $\begingroup$ @BrianBorchers The question doesn't present that as the definition of NP: it presents it as a definition of what a decision problem is. $\endgroup$ – David Richerby May 7 '15 at 6:58
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thank you! It makes a lot more sense now. So languages in NP are those that can verify membership in polynomial time, while languages in co-NP are those that can verify non-membership in polynomial time. My mistake was in believing that the (alleged) difference between this two classes resulted in some sort of running time difference in the algorithm that decides them, when that is not know to be the case. $\endgroup$ – diegovb May 7 '15 at 5:25
  • $\begingroup$ Right, polynomially verify a certificate. But you're right, it doesn't change the complexity of the overall problem, since you can just apply a boolean NOT to your final answer to get the opposite problem. $\endgroup$ – jmite May 7 '15 at 15:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.