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

1 Answer 1

4
$\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$
0

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.