1
$\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.

$\endgroup$
2
  • 1
    $\begingroup$ 4 Is correct, but the reasoning you gave was incorrect. $\endgroup$
    – nir shahar
    Commented Jul 21, 2021 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$ Commented Jul 21, 2021 at 16:57

1 Answer 1

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

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.