# Is the the complement of the Halting problem NP-hard [duplicate]

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$.

• 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. – Yuval Filmus Dec 23 '17 at 13:48
• I think you mean "$M$ doesn't halt on $x$". – Yuval Filmus Dec 23 '17 at 13:49
• You're right, thanks I corrected the question. – user3636583 Dec 23 '17 at 13:50
• Mind correcting the grammar? Halt(s) – candied_orange Dec 23 '17 at 13:51
• So Yuval the reduction you suggested is polynomial because M is of finite length and x depends on the input of the SAT-problem? – user3636583 Dec 23 '17 at 13:53