# Language in NPC and CoNP

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.

• 4 Is correct, but the reasoning you gave was incorrect. Jul 21, 2021 at 16:38
• 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 Jul 21, 2021 at 16:57

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