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!



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.