Bonus Homework 1
Remember the proof of the
Time Hierarchy Theorem
:
For each
t
(
n
)≥
n
,
DTIME
(
t
^{5}
(
n
)
)
⊃
DTIME
(
t
(
n
)
)
.
There is a mistake hidden in it!
Explain where, when, and why exactly the argument fails
and indicate how to mend it.
This will earn you 50 bonus points on your homework.