Why is the difference of two NP-complete languages not in NP?

Question

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?

Answer 1

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.

Answer 2

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}$.