edited by
1,442 views
1 votes
1 votes

If there is an $\rm NP$-complete language $L$ whose complement is in $\rm NP$, then the complement of any language in $\rm NP$ is in

  1. $\rm NP$
  2. $\rm P$
  3. Both (a) and (b)
  4. None of these
edited by

1 Answer

Best answer
2 votes
2 votes

$\def \NP {\rm NP}$ $\def \NPC {\rm NPC}$ $\def \co {\rm co \text -}$

(a) NP

 

Definition of $\co\NP$: If a language $L \in \NP$, then its complement $L' \in \co \NP$

 

Consider an arbitrary language $M \in \NP$. Thus, $M' \in \co\NP$. 

Since $L \in \NPC$, there is a polynomial time reduction from $M$ to $L$.

This means that there is a polynomial time reduction $R(x)$ such that $x \in M$ if and only if $R(x) \in L$. $$x \in M \Longleftrightarrow R(x) \in L$$

Also, $x \in M'$ if and only if $R(x) \in L'$. $$x \in M' \Longleftrightarrow R(x) \in L'$$

This usually only allows us to decide $M$ in $\NP$ time. To decide if $x \in M$, we can simply compute $R(x)$ in polynomial time, and check if $R(x) \in L$ in $\NP$ time.

If we try to decide $M'$, we need to solve $L'$ which is $\co\NP$, so we might not be able to solve it in $\NP$ time. (We don't know if $\NP = \co\NP$)

However, if our $L$ is such that $L \in \NPC$ and $L' \in \NP$, then we can also decide $M'$ in $\NP$ time.

Thus, no matter what problem $M \in \NP$ we have, we can decide both $M$ and $M'$ in $\NP$ time. Which means $\NP = \co\NP$


What about option (b)?

Even if the complexity classes $\NP$ and $\co\NP$ collapse into one, the $\rm P$ vs $\NP$ question remains open. Our assumed language $L$ doesn't imply option (b).

selected by

Related questions

11 votes
11 votes
2 answers
1
sourav. asked Sep 9, 2017
4,534 views
My Question $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$I have to check that it is Turing Recogniza...
0 votes
0 votes
0 answers
2
commenter commenter asked Jun 13, 2019
358 views
I know that all NP problems can be reduced to Boolean Satisfiability SAT problem. But my question is whether SAT problem can be reduced to other NP complete problems like...