Here are a couple of questions I struggle with. (We use $A'$ to denote the complement of the problem $A$.)
- A problem $A$ is NP-complete if and only if $A'$ is in NP?
- 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?
\emptyset
, $\emptyset$) is not NP-complete, nor is its complement. $\endgroup$