It's not only NP-hard, it's undecidable!
For the easy proof, use Rice's Theorem. This is a non-trivial semantic property, so it's undecidable (and thus NP-hard). Done.
For a more interesting proof:
For any Turing machine $T$, let's define a new machine $Z_T$ like this:
$Z_T$ looks at the first symbol on the tape. If it's a 1
, it moves to the right and runs $T$ on the remainder of the tape. If it's anything else, it loops forever.
Now, suppose there exists a machine $U$ that can decide UNIQUE
. I'm going to use this machine to decide the "Any-Input Halting Problem" ("is there any input that will make this machine halt?"), which is known to be undecidable (and NP-hard).
For any Turing machine $T$ that you give me, I can create a $Z_T$. Then I run $U$ on $Z_T$. I know that, for the input 0
, $Z_T$ will loop forever. I also know that $Z_T$ halts on input 1XYZ
only if $T$ halts on input XYZ
. Therefore, $U$ will accept $Z_T$ if and only if $T$ halts on some input.
Since we know the Any-Input Halting Problem can't be decided, this hypothetical $U$ can't exist. Therefore UNIQUE
is also undecidable, and anything undecidable is also NP-hard.