tag:blogger.com,1999:blog-3722233.post5098483086430402942..comments2024-06-24T15:24:01.378-05:00Comments on Computational Complexity: A New Proof of the Nondeterministic Time HierarchyLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-3722233.post-9714686343727773982016-02-08T11:42:54.087-06:002016-02-08T11:42:54.087-06:00Nice! It solves an open problem posed in our book,...Nice! It solves an open problem posed in our book, asking whether the exponential "gap" in the standard proof is inherent. Sanjeev Arorahttps://www.blogger.com/profile/10896480884587733715noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7794776176145197842012-10-19T16:16:58.299-05:002012-10-19T16:16:58.299-05:00For deterministic computation you need an extra lo...For deterministic computation you need an extra log factor for the simulation, technically a log factor to reduce from k-tapes to 2-tapes. For nondeterministic there is a way to get from k-tapes to 2-tapes without an extra log overhead. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8423606490040326702012-10-19T08:25:45.482-05:002012-10-19T08:25:45.482-05:00Dear Lance, it looks like the proof also works for...Dear Lance, it looks like the proof also works for deterministic machines. So, we should have DTIME(t1(n)) strictly contained in DTIME(t2(n)) as soon as t1(n+1) = o(t2(n)) and both t1, t2 time constructible. But then where is the log factor that usually appears in deterministic time hierarchy? <br /><br />--Martin & Stephan from MunichAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24595444858563672602011-09-09T10:04:40.355-05:002011-09-09T10:04:40.355-05:00I guess machine M actually needs to check if |y|=t...I guess machine M actually needs to check if |y|=t_2(i+m+2). That seems to work. (Note: the error, if it is one, appears to be in the paper as well.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33374811077945293752011-09-09T09:22:29.223-05:002011-09-09T09:22:29.223-05:00I'm trying to give this proof in class, but am...I'm trying to give this proof in class, but am missing something. Consider the reverse direction. Say $1^i 0 1^m 0 \not\in L(M)$. Then we know that M_i rejects on all computation path. But M_i runs in time O(t_1(n)), not t_1(n). So maybe all its computation paths have length 2t_1(n), say. (And I don't think you can use the speedup theorem here, without allowing y to be non-binary. Isn't that right?) So then M_i rejects on computation path y for all y of length 2t_1(n). But then the argument stops.<br /><br />What am I missing?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74636385739720103982011-04-07T05:32:08.639-05:002011-04-07T05:32:08.639-05:00We publish all comments good and bad. We moderate ...We publish all comments good and bad. We moderate to stop the ugly.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24809023247887736092011-04-07T01:13:56.516-05:002011-04-07T01:13:56.516-05:00Btw, I really wonder if my previous comment goes t...Btw, I really wonder if my previous comment goes through moderation - on one hand, it is not offensive at all, on the other, it does not add much, so it might seem immodest if you let it appear. Meta: Will this comment go through?domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44792709110899471102011-04-07T01:02:57.714-05:002011-04-07T01:02:57.714-05:00Brilliant proof!Brilliant proof!domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59226687428764736002011-04-06T08:08:55.420-05:002011-04-06T08:08:55.420-05:00Michaël: Good catch. Fixed.
Or: In the second bul...Michaël: Good catch. Fixed.<br /><br />Or: In the second bullet, M only simulates M_i on the single path described by y. <br /><br />Anon 5: Zàk's proof automatically works for any measure that has universal simulation (like Sigma_5-Time). It's much harder to generalize our techniques.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71491223909618215942011-04-06T04:16:44.038-05:002011-04-06T04:16:44.038-05:00OK, I see it now. Thanks to Arnab Bhattacharyya fo...OK, I see it now. Thanks to Arnab Bhattacharyya for a patient explanation.<br /><br />Very nice proof!Or Meirnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64241430788206941332011-04-06T02:36:34.906-05:002011-04-06T02:36:34.906-05:00The proof is amazingly compact. It's only 10 l...The proof is amazingly compact. It's only 10 lines long, which gives it elegance, sort of a Sudoku square stripped to its essential clues from which the full solution can be expanded. I'm stuck (I didn't get today's Sudoku either though), here's where. The proof defines a machine M. There are two clauses in the definition: M accepts if condition 1, and M accepts if condition 2. So I provisionally believe that M is a machine which can never reject anything, as that's not in its nature. But later in the proof there's a clause "M rejects", at least I think it's M and not some other indexed nondeterministic Turing machine, which threatens my provisional belief. Back to square 1 !Mickihttps://www.blogger.com/profile/11592612022853202507noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47389153391759568942011-04-05T21:19:24.462-05:002011-04-05T21:19:24.462-05:00What "broader set of complexity measures"...What "broader set of complexity measures" are you referring to?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4908033986607113382011-04-05T18:44:24.630-05:002011-04-05T18:44:24.630-05:00Hi Lance,
Could you explain why does the machine M...Hi Lance,<br />Could you explain why does the machine M run in non-deterministic time t_2?<br /><br />I am probably missing something, but don't you need need time of at least 2^t_1(n) in order to emulate M_i on all possible computation paths?<br /><br />Thanks!<br />OrOr Meirnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48065024829836258462011-04-05T16:21:07.282-05:002011-04-05T16:21:07.282-05:00Now I feel Lance's proof is fine.
It does not...Now I feel Lance's proof is fine. <br />It does not need any revision. <br />It is a very nice proof for this<br />important theorem.<br /><br />BinAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70675677641020716962011-04-05T13:00:52.844-05:002011-04-05T13:00:52.844-05:00Bin Fu: I'm not sure it would make any differe...Bin Fu: I'm not sure it would make any difference. Maybe the error there is that "|y|=t_1(m)" should read "|y| = t_1(m+i+2)" ?Michaëlhttps://www.blogger.com/profile/02377285634686958683noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84838648892240211472011-04-05T11:36:50.450-05:002011-04-05T11:36:50.450-05:00I believe that t_2(|w|) in the line of the first b...I believe that t_2(|w|) in the line of the first bullet is t_1(|w|).<br /><br />Bin FuAnonymousnoreply@blogger.com