CODEWITHSUNDEEP
turing-machinesnpnp-harddecidable
acagu
acagu

Reputation: 33

How to prove that the language $E_{tm}$ is $NP-Hard$

Consider the language $E_{tm}={ \langle M \rangle: M\text{is a Turing Machine that accepts nothing}$

I am not sure how to even start. My idea is to provide poly time reduction from some NP - Complete problem. E_tm

What I don't understand is that, knowing that E_tm is not decidable, but NP-Hard class is decidable.

Upvotes: 0

Views: 2644

Answers (1)

acagu
acagu

Reputation: 33

solution:

DF: A problem is NP-hard if all problems in NP are polynomial time reducible to it, even thoughit may not be in NP itself ( p326 Sipser) (the only definition our book has ). For any language L' that is in NP if we show that we can poly-time reduce to Etm. This will prove that that Etm is NP - hard. Since L' is in NP by definition there exist a TM ( NTM but since they are equivalent in power I write TM ) M' such that decides L'.

TM M'' that takes as an input <M,w> constructs
TM M' such that
 on arbitrary x
if w = x
  run M on w if accept => reject
                     if reject => accept
else reject.

Therefore M accepts w iff M'' rejects all the input. Let's confirm that. First assume that M accepts w, then M'' reject on any input therefore L(M'') = empty. Now assume that M rejects w, then M'' accept, therefore L(M'') is not empty. Note that to construct the M'' takes polynomial time. That completes the proof.

Upvotes: 2

Related Questions