HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMinor

Why does the time hierarchy theorem use a rather intricate diagonal argument?

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#130415, answer score: 6

Revisions (0)

No revisions yet.