0
$\begingroup$

Let $A_{TM}=\{<M,w>|M~is~a~TM~and~M~accepts~w\}$, clearly it is NP-Hard.

Let $M_{A_{TM}}$ be the DTM that recognizes $A_{TM}$.

Define $M_⤭$ to be the TM obtained from $M$ by swapping the accept and reject states.

I assume that $L(M_{A_{TM}⤭})\ne \overline{A_{TM}}$, because if we swap the accept and reject states, we do not know anything about the situation where we have a not-halting TM.

I trouble in writing the exact formation of $L(M_{A_{TM}⤭})$, and I have trouble proving it is NP-Hard.

Any help / hints?

Thanks a lot!

Improve this question
$\endgroup$

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.