# Complement of NP-complete can be in NP

Here are a couple of questions I struggle with. (We use $$A'$$ to denote the complement of the problem $$A$$.)

1. A problem $$A$$ is NP-complete if and only if $$A'$$ is in NP?
2. A class problem $$A$$ is NP-Complete iff $$A'$$ is in NP? (Is there any difference between these two?)

I got this claim to be true that

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

And this claim also to be true:

$$A$$ is NP-hard iff $$A'$$ is coNP−hard

Then is the upper claim also true?

• The claim is false. Consider $A = \emptyset$. – Yuval Filmus Apr 23 '19 at 4:05
• I havenot got. If A=phi , then A and A' both in phi . right? – Srestha Apr 23 '19 at 4:51
• then how this claim is true that "If there is an NP-complete language L whose complement is in NP, then the complement of any language in NP is in NP" – Srestha Apr 23 '19 at 4:53
• @Srestha The empty set (\emptyset, $\emptyset$) is not NP-complete, nor is its complement. – Raphael Apr 23 '19 at 6:18
• I answered as much of your question as I could understand (below) but I don't know what you mean by "a class problem" or "the upper claim". – David Richerby Apr 23 '19 at 9:11

A problem $$A$$ is NP-complete if and only if $$A'$$ is in NP?
This is false. Take $$A'=\emptyset$$: then we have $$A'\in\mathrm{NP}$$ but $$A=\Sigma^*$$ is not $$\mathrm{NP}$$-complete.
If there is an NP-complete language $$L$$ whose complement is in NP, then the complement of any language in NP is in NP.
1. The complement of an $$\text{NP}$$-complete problem is $$\text{co-NP}$$-complete;
2. if any $$\text{co-NP}$$-complete problem is in a class $$\mathcal{C}$$ that is closed under polynomial-time reductions, then every $$\text{co-NP}\subseteq\mathcal{C}$$;
3. $$\text{NP}$$ is closed under polynomial-time reductions.