3
$\begingroup$

I found something in my notes I don't really understand, maybe you could help.

Let $A$ = Independent Set and $B$ = Clique. Then, we clearly have

  • $A \in \mathsf{NPC}$ and
  • $B \in \mathsf{NP}$.

Now, the claim is that $A \setminus B \notin \mathsf{NP}$ with the following explanation. If it was in $\mathsf{NP}$ then $\mathsf{NP} = \mathsf{NPC}$.

Can you explain why this argument is true?

$\endgroup$
4
$\begingroup$

It's a bit artificial, but if we define

$A = \{(G,k):G \text{ has an independent set of size } k \}$

$B = \{(G,k):G \text{ has a clique of size } k \}$

then $A \setminus B$ is $\mathsf{coNP}$-hard because we can reduce $\overline{B}$ to it: given a graph $G$ and a number $k$ we can form $G'$ by adding $k$ isolated vertices to $G$, then $(G',k) \in A\setminus B$ iff $(G,k) \in \overline{B}$.

I claim that

$A \setminus B \in \mathsf{NP} \Leftrightarrow \mathsf{NP}=\mathsf{coNP}$

$(\Rightarrow)$: If a $\mathsf{coNP}$-hard language is in $\mathsf{NP}$, then $\mathsf{NP}=\mathsf{coNP}$.

$(\Leftarrow)$: If $\mathsf{NP}=\mathsf{coNP}$ then $A \setminus B \in \mathsf{NP}$ follows by closure properties of $\mathsf{NP}$.

Since researchers believe that $\mathsf{NP} \neq \mathsf{coNP}$ (this is a stronger version of $\mathsf{P} \neq \mathsf{NP}$), it makes sense to bet on $A \setminus B \notin \mathsf{NP}$. Currently we have no proof though.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You are right, one needs to assume even more. (I removed our obsolete comments). $\endgroup$ – Raphael Aug 28 '13 at 10:47
2
$\begingroup$

The difference between two $\mathsf{NP}$ languages is not necessarily in $\mathsf{NP}$. (It might be, but it might not be.)

Consider $A=\{0,1\}^*$ and $B$ any $\mathsf{NP}$-complete language (e.g., 3SAT). Then $A \setminus B = \overline{B}$ is the complement of $B$. Since $B$ is $\mathsf{NP}$-complete, by definition $\overline{B}$ is $\mathsf{coNP}$-complete. Now if any $\mathsf{coNP}$-complete language is in $\mathsf{NP}$, it follows that $\mathsf{NP}=\mathsf{coNP}$. This would be a very surprising result.

To summarize: Most researchers believe that $\mathsf{NP}\ne \mathsf{coNP}$ (just like they believe that $\mathsf{P}\ne \mathsf{NP}$); and if we assume that $\mathsf{NP}\ne \mathsf{coNP}$, it follows that there exists languages $A,B \in \mathsf{NP}$ such that $A\setminus B\notin \mathsf{NP}$.

In other words, under plausible assumptions, the difference between two $\mathsf{NP}$ languages is not necessarily in $\mathsf{NP}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That's a nice answer. However, it is not clear why the situation should not be clearer for $A,B$ fixed as in the question. $\endgroup$ – Raphael Aug 28 '13 at 10:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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