0
$\begingroup$

I know that $A_{TM}=\{<M,w>|M~is~a~TM~and~M~accepts~w\}$ is NP-Hard:

By showing a polynomial time reduction - $A \le_p A_{TM}$:

Let $A \in NP$, then there exists a $NTM$ that decides $A$ in polynomial time, thus there exists a $DTM$ $M_A$ that decides $A$ in exp time.

Then $f(w)=<M_A,w>$ is the reduction, so $A_{TM}$ is NP-Hard.

Does it mean that $\overline{A_{TM}}$ is co-NP Hard since it is $A_{TM}$'s complement?

Thanks!

$\endgroup$
4
  • $\begingroup$ Which definition of co-NP-hard are you using? Under what types of reductions? $\endgroup$
    – D.W.
    Feb 12, 2023 at 4:38
  • $\begingroup$ @D.W. Correct, polynomial mapping reduction $A \le_P \overline{A_{TM}}$. Thanks! $\endgroup$
    – Geo
    Feb 12, 2023 at 8:16
  • $\begingroup$ 1. Please edit the question to clarify. We want questions to be self-contained, so people don't have to read the comments to understand what is being asked. 2. What have you tried? Have you tried to construct an explicit reduction? What have you come up with? Have you tried applying the formal definition? $\endgroup$
    – D.W.
    Feb 12, 2023 at 8:42
  • $\begingroup$ @D.W. I tried to use the same procedure as for $A_{TM}$, but I don't think that the same reduction works, correct me if I'm wrong. $\endgroup$
    – Geo
    Feb 12, 2023 at 10:26

1 Answer 1

0
$\begingroup$

Yes, let's show this in $2$ ways.

Option A

Let $B\in Co-NP$. As such, there exists a NTM, say $N_B$, such that for any $b$: if $b\notin B$ then $N_B$ rejects in a polynomial time. We can also say there exists a DTM, say $M_B$, such that for any $b\notin B$ it rejects it in (at most) exp time. We therefore reduce any $b$ to: $<M_B,b>$. Note that $|M_B|$ is constant, therefore the reduction is polynomial. This is the same argument as the one you presented.

Option B

Ignore the above, simply use the fact $\overline{B}\in NP$, and therefore a reduction exists $\overline{B}\leq_P A_{TM}$. The exact same reduction works $B\leq_P \overline{A_{TM}}$.

Conclusion

We showed $B\leq_P \overline{A_{TM}}$. We chose $B$ as an arbitrary language in $Co-NP$. It follows that $\overline{A_{TM}}$ is $Co-NPH$.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you for the answer! :) $\endgroup$
    – Geo
    Feb 12, 2023 at 19:18

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.