There exists a TM $M$ such that both $L(M)$ and $L\left(M_{\star}\right)$ are NP-Hard

47 Views Asked by At

I need to prove the following :

Assume the $P\ne NP$

There exists a TM $M$ such that both $L(M)$ and $L\left(M_{\star}\right)$ are NP-Hard. let $L\left(M_{\star}\right)$ be the TM obtained from $M$ by swapping the accept and reject states.