Let the class of languages $$X = \{ L \ | \ L\in NPC \land L\in coNPC\}$$
Why is it true that $NP \ne coNP \implies X = \emptyset$?
$\begingroup$
$\endgroup$
11
-
3$\begingroup$ because every $L$ can be reduced to an NPC (/coNPC) language. Thus if there one $L$ in the intersection, all can be reduced to both NP and coNP and they will be equal. $\endgroup$– Ran G.Jun 20, 2015 at 14:27
-
2$\begingroup$ Side question: does it really help you to ask so many questions? I mean, the fun in this topic is ponder on these questions. Mind it may take 1-4 hours to solve each, but it would be very fulfilling to do that yourself. I'm not saying you shouldn't use this site to get idea, but i'm just suggesting to put enough thought (~2-3 hours!) in each question before --- this is the fun part!! (at least, this was the fun part for me, when I was studying this material). If you don't think so, I'd be happy to discuss it in the Computer Science Chat. $\endgroup$– Ran G.Jun 20, 2015 at 14:30
-
$\begingroup$ @RanG. Congratulations for making it to 10K rep! $\endgroup$– Rick DeckerJun 20, 2015 at 14:41
-
$\begingroup$ @RanG., When you say "every $L$", do you mean every $L\in NP \cup coNP$? $\endgroup$– EliminationJun 20, 2015 at 14:56
-
2$\begingroup$ as for the side note: Yes, you will fail sometimes. So what? only those who don't do, never fail. PS. to ask a question after you have exhausted your thoughts and failed, is WAY MORE powerful towards your understanding. Try it, and see if I'm wrong. $\endgroup$– Ran G.Jun 20, 2015 at 16:42
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
0
Summarizing the comment as an answer:
Consider $L\in NPC$. By definition it means that every $A\in NP$ satisfies $$ A\le_p NPC.$$ Similarly, if $L\in coNPC$, then by definition (which is not very common, but we can defined it in similar way to NPC), every $B \in coNP$ satisfies $$B\le_p coNPC.$$
So assume $X$ is non-empty, that is, there is $L$ which is both NP-complete, and coNP-complete.
Now, $L$ is in $NP$ (since $NPC\subseteq NP$), but it is also in $coNP$ from a similar reason. From here we will get that $NP=coNP$. Assume not, so there is a language $A\in NP$ but $A\notin coNP$ (or the other way). But $A\le_p L$ since $L$ is complete for $NP$. This means $A$ can be reduced to a $coNP$ language (L!), which implies that $A\in coNP$, a contradiction. More generally, this reasoning implies that $NP \subseteq coNP$, and the other direction holds symmetrically. Thus $NP=coNP$ under these assumptions.
