0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ The claim is false. Consider $A = \emptyset$. $\endgroup$ – Yuval Filmus Apr 23 at 4:05
  • $\begingroup$ I havenot got. If A=phi , then A and A' both in phi . right? $\endgroup$ – Srestha Apr 23 at 4:51
  • $\begingroup$ 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" $\endgroup$ – Srestha Apr 23 at 4:53
  • 1
    $\begingroup$ @Srestha The empty set (\emptyset, $\emptyset$) is not NP-complete, nor is its complement. $\endgroup$ – Raphael Apr 23 at 6:18
  • 1
    $\begingroup$ 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". $\endgroup$ – David Richerby Apr 23 at 9:11
3
$\begingroup$

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.

This follows from the following three facts, which you should attempt to prove yourself.

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

Your Answer

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.