Let us define the language (the complement of the Halting Problem):

$$ LOOPING = \left\{ \langle M,x \rangle | M \ doesn't \ halt \ on \ x\right\} $$

The question is if $LOOPING$ is NP-Hard. I'm pretty clueless about the answer. I know the the Halting problem is NP-Hard, but I can't seem to find a reduction from an NP-Hard problem to $LOOPING$.

  • $\begingroup$ Hint: Construct a Turing machine which goes over all potential satisfying assignments of a SAT instance, halts if it doesn't find any, and enters an infinite loop otherwise. $\endgroup$ – Yuval Filmus Dec 23 '17 at 13:48
  • $\begingroup$ I think you mean "$M$ doesn't halt on $x$". $\endgroup$ – Yuval Filmus Dec 23 '17 at 13:49
  • $\begingroup$ You're right, thanks I corrected the question. $\endgroup$ – user3636583 Dec 23 '17 at 13:50
  • $\begingroup$ Mind correcting the grammar? Halt(s) $\endgroup$ – candied_orange Dec 23 '17 at 13:51
  • $\begingroup$ So Yuval the reduction you suggested is polynomial because M is of finite length and x depends on the input of the SAT-problem? $\endgroup$ – user3636583 Dec 23 '17 at 13:53