Jump to content

Talk:Time hierarchy theorem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 68.43.197.36 (talk) at 04:19, 3 October 2004 (Stronger bound, link to proof). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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)

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.