Remix.run Logo
meindnoch 6 days ago

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

jhanschoo 6 days ago | parent | next [-]

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.

JohnKemeny 5 days ago | parent | prev [-]

Well, since you said "for any function f" ... It's not true for, say, constant functions.

meindnoch 5 days ago | parent [-]

How's that so?

Calculating 2^C for any fixed C is an asymptotically constant-time operation.