[Solved]: Why is the difference of two NP-complete languages not in NP?

Problem Detail: 

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?

Asked By : AC9000

Answered By : sdcvvc

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13955

3.2K people like this

 Download Related Notes/Documents