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

## marked as duplicate by quicksort, David Richerby, Evil, Community♦Dec 24 '17 at 9:21

• I think you mean "$M$ doesn't halt on $x$". – Yuval Filmus Dec 23 '17 at 13:49