1
$\begingroup$

$A$ is NP-hard iff $\overline{A}$ is $coNP$-hard, where $\overline{A}$ does mean complement of $A$.

I can't figure out why it is true. Let $A\in NP-hard$. I know that each problem in $NP$ is polynomially reducible to $A$. So, let's "negate" $A$, then by definition: $\overline{A}\in coNP$. However, I am not sure why $\overline{A}\in coNP-hard$. Could you explain it me ?

My intution is that $NP$ and $coNP$ contains only decision problems, using this fact we can use machine for $A$ and negate answer.

$\endgroup$

2 Answers 2

1
$\begingroup$

Definition: co$NP = \{A \mid \overline{A} \in NP \}$
Claim: $A$ is $NP$-hard iff $\overline{A}$ is co$NP$-hard.
Proof:
Assume $A \text{ is } NP\text{-hard}$ ($\Rightarrow$). Then by definition $$ \forall L \in NP, \ \ x \in L \Longleftrightarrow f(x) \in A \ \ (\text{ polynomial reducible})$$ equivalently $$ \forall L \in NP, \ \ x \notin L \Longleftrightarrow f(x) \notin A \ \ (\text{ polynomial reducible})$$ implies $$ \forall L \in NP, \ \ x \in \overline{L} \Longleftrightarrow f(x) \in \overline{A} \ \ (\text{ polynomial reducible})$$ meaning $\overline{L} \in$ co$NP$ and reducible to $\overline{A}$, and thus $\overline{A} \text{ is co}NP\text{-hard}$.

Assume $\overline{A} \text{ is co}NP\text{-hard}$ ($\Leftarrow$). Then moving in the backward direction as above:

$$ \forall L \in NP, \ \ x \in \overline{L} \Longleftrightarrow f(x) \in \overline{A} \ \ (\text{ polynomial reducible})$$ equivalently $$ \forall L \in NP, \ \ x \notin L \Longleftrightarrow f(x) \notin A \ \ (\text{ polynomial reducible})$$ and so $$ \forall L \in NP, \ \ x \in L \Longleftrightarrow f(x) \in A \ \ (\text{ polynomial reducible})$$ meaning $A$ is $NP$-hard.


Update:

If $L \in NP$ then there exists a NDTM $M_1$ running in polynomial time such that:

  • if $x\in L$ then $M_1(x)=\text{"yes"}$ for some computation paths of $M$.
  • if $x\notin L$ then $M_1(x)=\text{"no"}$ for all computation paths of $M_1$.

If $L \in coNP$ then there exists a NDTM $M_2$ running in polynomial time such that:

  • if $x\in L$ then $M_2(x)=\text{"yes"}$ for all computation paths of $M_2$.
  • if $x\notin L$ then $M_2(x)=\text{"no"}$ for some computation paths of $M_2$.
$\endgroup$
1
1
$\begingroup$

This argument is given for any complexity class.

If $C$ is a complexity class (for your question NP) and $L$ is $C-Hard$ (an 'identical' argument can be for complete languages):

If $A \in coC$ so $\bar A \in C$ so $ \bar A \le L$: ($\phi$ is the Karp-reduction for that matter)

$ \exists \phi.x\in \bar A \iff \phi(x)\in L $

Since it's iff the negation is:

$ \exists \phi.x\notin \bar A \iff \phi(x) \notin L$

Hence, (by definition of complementary)

$ \exists \phi.x\in A \iff \phi(x) \in \bar L$

$A \le \bar L \implies \bar L \in coC-Hard$

Negating the answer of an NP Turing machine won't help you to decide a language in coNP (except for trivial cases like language in P), since by definition an NP Turing machine accepts iff there exist an accepting branch in its' computation.

For simplicity, assume your NP Turing machine always has a rejecting branch in every computation (we can assume it for every NP Turing machine, why?), negating the answer will result in the trivial language $\Sigma $* every-time.

$\endgroup$

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.