2
$\begingroup$

A few days ago I had a test that I failed to pass, and it had a question that I failed to do.

the question:

given:

$A \in NPC$

$A \in CoNP$

Determine which of the following statements is correct:

  1. $P\neq NP$
  2. $P\neq CoNP$
  3. $NP\neq CoNP$
  4. $NP=CoNP$
  5. None of the above claims are true.

My idea to solve this, is to choose a language $B \in P$. From language $B$ it is possible to make a reduction to both problems to $CoNP$ and $NPC$. And take the complementary B language, $B^{'}$, which also belongs to the 2 groups.

Because B and B complement an identity then, it is possible to get that $NP = CoNP$ and $NPC = CoNPC$ , but I do not know if I am right in this solution.

I think 4 is the correct answer, but I do not know why the other answers are incorrect.

New contributor
masterHaham is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
2
  • 1
    $\begingroup$ 4 Is correct, but the reasoning you gave was incorrect. $\endgroup$ – nir shahar Jul 21 at 16:38
  • $\begingroup$ Thanks for the comment, can you please tell me why 4 is true, it is not clear to me, how from the fact that A in both NPC and CoNP, 4 is true $\endgroup$ – masterHaham Jul 21 at 16:57
2
$\begingroup$

Let $L\in NP$. Thus, $L\le_p A$. Since $A\in coNP$, then $L\in coNP$. Hence, $NP\subseteq coNP$.

Now, let $L\in coNP$. Thus, $\overline{L} \in NP$ and therefore $\overline{L}\le_p A$. From reduction properties, we know that $L\le_p \overline{A}$ holds as well. Now, since $A\in coNP$ then $\overline{A}\in NP$. Hence, $L\in NP$, and therefore we get that $coNP\subseteq NP$

Now we can conclude that $NP\subseteq coNP$ and $coNP\subseteq NP$ and hence $NP=coNP$.

$\endgroup$

Your Answer

masterHaham is a new contributor. Be nice, and check out our Code of Conduct.

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.