tag:blogger.com,1999:blog-3722233.post108981244971229525..comments2024-06-16T05:18:05.629-05:00Comments on Computational Complexity: Time and Space HierarchiesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-1090358600987300332004-07-20T16:23:00.000-05:002004-07-20T16:23:00.000-05:00Actually, the name should by (in Tex) \v{Z}\'{a}k ...Actually, the name should by (in Tex) \v{Z}\'{a}k (hacek over Z is missing). The Czech language is strange:-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1089856444921862302004-07-14T20:54:00.000-05:002004-07-14T20:54:00.000-05:00I'm curious about the log t1(n) term in the DTIME ...I'm curious about the log t1(n) term in the DTIME hierarchy. Is this a tight bound, or is it open as to whether this term can be reduced or eliminated? Sipser mentions in passing that this is an open question, but he used a 1-tape TM model in his exposition. I understand that if the number of tapes are fixed for some k >= 2, that the log t1(n) term can be eliminated altogether [Furer 1982].Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1089837734299972042004-07-14T15:42:00.000-05:002004-07-14T15:42:00.000-05:00Dear Lance,
I always see these results in the fir...Dear Lance,<br /><br />I always see these results in the first few sections of any complexity text. I am curious about other resuts that use the Hierarchy Theorems. For example, the DTIME hierarchy shows that P is a proper subset of EXP. What else can be said with these theorems? They seem quite applicable, and it would be nice to know about other results stem from them. Also, maybe you could do a post on the Polynomial Hierarchy since I have yet to find a lucid explanation of what that is all about. Thanks!<br /><br />Steve Orzel<br />phloam@myrealbox.comAnonymousnoreply@blogger.com