Talk:Time hierarchy theorem
 | Time hierarchy theorem received a peer review by Wikipedia editors, which is now archived. It may contain ideas you can use to improve this article. |
Proof looks basically OK. It needs a justification of how a Turing machine can simulate M in O(f(n)³); "it is safe to say" is a bit weak. The fact that f is time-constructible need to be used explicitly in the proof. Also, we need an article on time-constructible function explaining why the concept is important and the exciting things you can do with functions that are not time-constructible. Gdr 23:41, 2004 Jul 4 (UTC)
Stronger bound, link to proof
The time heirarchy theorem has actually been proved for a much stricter bound. Specifically, TIME(o( f(n)/log(f(n)) )) is a strict subset of TIME(O(f(n)) -- sorry for the lack of pretty LaTeX. Lecture notes with proof here. I'm sorry I don't have time to update the article myself, but I thought I'd at least drop a comment with the information and a link.
Where's the linear lower bound come from?
I often see this result stated with a linear (n) lower bound on t(n). I can only think it must be because no smaller functions are time-constructible (a Turing machine can't even read an input of size n in sublinear time, although it can read it in sublinear work tape space), so it's actually redundant, in the same way that requiring NP proof signatures to have polynomial size is redundant. It might still be useful to mention somewhere though, since it does effectively limit the power of the theorem. Deco 28 June 2005 16:59 (UTC)