gotchaMinor
Why does the time hierarchy theorem use a rather intricate diagonal argument?
Viewed 0 times
whytheargumentdiagonalhierarchytimeratherintricatetheoremdoes
Problem
Isn't it possible to prove it by defining some problem that can be solved in $f(n)^2$ in the worst case due to its output always being $f(n)^2$ characters so that it won't be solvable in $f(n)$?
Where am I wrong?
Where am I wrong?
Solution
The output size does not scale with (time) complexity of problems in general.
In fact, complexity theorists are largely interested in decision problems for which the output will either be 0 or 1.
In fact, complexity theorists are largely interested in decision problems for which the output will either be 0 or 1.
Context
StackExchange Computer Science Q#130415, answer score: 6
Revisions (0)
No revisions yet.