0
$\begingroup$

This is in regards to a specific TM:

$UNIQUE: \{$ TM | TM loops on at least an input, and TM also halts on at least one input $\}$

This is a play on the Halting Problem, where it basically combines $HP$ as well as $\overline{HP}$ into one. We know that $HP$ is NP-Hard, we also know that $\overline{HP}$ is NP-Hard, but would combining the two also be NP-Hard? How would the proof for this go?

$\endgroup$
2
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Mar 26, 2019 at 20:24
  • $\begingroup$ Removed my work and instead made it more conceptual, does this work or should I make further changes? $\endgroup$ Mar 26, 2019 at 20:37

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ @AndrewRaleigh Undecidable is "harder" than NP-hard, so anything that's undecidable must also be NP-hard. NP-hard means you can't solve it in polynomial time without some extra information (unless P=NP). Undecidable means you can't solve it at all, no matter how much time you have—therefore you certainly can't solve it in poly-time. $\endgroup$
    – Draconis
    Mar 27, 2019 at 14:43
  • 1
    $\begingroup$ @AndrewRaleigh Sure, replace every instance of "undecidable" with "NP-hard" in the proof :P and I guess show that $Z_T$ adds only a constant overhead $\endgroup$
    – Draconis
    Mar 27, 2019 at 15:17
  • 1
    $\begingroup$ It is not true that every undecidable problem is NP-hard. Take the Halting problem, and space it out with exponentially many 1s. The resulting language is Turing-equivalent to the Halting problem, but cannot really help polytime reductions at all, because these can't access the useful bits. $\endgroup$
    – Arno
    Mar 27, 2019 at 15:47
  • 1
    $\begingroup$ @AndrewRaleigh Yes, here it works. The totality problem is indeed NP-hard, and the reduction given by Draconis is a polytime reduction. $\endgroup$
    – Arno
    Mar 27, 2019 at 17:50
  • 1
    $\begingroup$ @Arno Isn't it still NP-hard, just not NP-complete (since it can't be decided in polynomial time, but also can't be verified in polynomial time)? $\endgroup$
    – Draconis
    Mar 27, 2019 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.