←back to thread

The Halting Problem is a terrible example of NP-Harder

(buttondown.com)
108 points BerislavLopac | 1 comments | 17 Apr 25 07:34 UTC | HN request time: 0.29s | source
Show context
meindnoch ◴[17 Apr 25 09:34 UTC] No.43714637[source]▶
For any function f(n) the problem "compute 2^f(n)" is going to be Ω(f(n)), because the output is f(n) bits; so merely writing down the answer takes Ω(f(n)) steps.

Note, that the number n is the input here, which is k = log(n) bits long. So the runtime is actually Ω(f(2^log(n))) = Ω(f(2^k)).

replies(2): >>43714700 #>>43717124 #
1. jhanschoo ◴[17 Apr 25 09:43 UTC] No.43714700[source]▶
This is indeed as trivially true as you say, but this is not a decision problem, which is what the article is discussing. That said, you can use diagonalization over turing machines to construct a language that is indeed strictly more difficult.