tag:blogger.com,1999:blog-3722233.post200380198..comments2024-10-10T06:29:39.038-05:00Comments on Computational Complexity: Foundations of Complexity Lesson 19: The Immerman-Szelepcsenyi TheoremLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-5269448997393839572010-04-18T13:55:47.556-05:002010-04-18T13:55:47.556-05:00You are right. Thank you for the replies!You are right. Thank you for the replies!Daniel Lorchhttps://www.blogger.com/profile/04302402740280438773noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16977178428437576642010-04-16T14:15:49.819-05:002010-04-16T14:15:49.819-05:00We need to make sure m_{i+1} is correct on every n...We need to make sure m_{i+1} is correct on every nondeterministic path that doesn't reject. Your algorithm could undercount m_{i+1} causing problems later.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80072522272070563862010-04-15T13:08:27.050-05:002010-04-15T13:08:27.050-05:00This is my suggestion for the second algorithm. Wh...This is my suggestion for the second algorithm. Why can't we just use nondeterminism to "guess" the path to n+1 ?<br /><br />Let mi+1=0<br />For all configurations C<br /> Guess a path from I to C in at most i+1 steps<br /> If found<br /> Let mi+1=mi+1+b<br /><br />I think I might be misunderstanding nondeterminism. Maybe it is related to the fact that the <i>nondeterministic</i> turing machine needs to be able to provide a certificate, which can then be verified by the <i>deterministic</i> machine.<br /><br />In my algorithm, the certificate would be the set of all reachable nodes. Maybe I am violating the space bound with that? I am confused..Daniel Lorchhttps://www.blogger.com/profile/04302402740280438773noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20560798525667395602010-04-15T13:01:10.235-05:002010-04-15T13:01:10.235-05:00This comment has been removed by the author.Daniel Lorchhttps://www.blogger.com/profile/04302402740280438773noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64151669765795182802010-04-15T11:01:26.762-05:002010-04-15T11:01:26.762-05:00How is it even possible that we compute the set of...How is it even possible that we compute the set of all non-accepting configurations? Wouldn't that require exponential space?Daniel Lorchhttps://www.blogger.com/profile/04302402740280438773noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3497024448165795962010-04-15T10:57:05.115-05:002010-04-15T10:57:05.115-05:00Let me try to modify the algorithm just a little:
...Let me try to modify the algorithm just a little:<br /><br />Let r=0<br />For all accepting configurations C of M(x)<br /> Try to guess a computation path from I to C<br /> If found let r=r+1<br />If r>0 then reject o.w. accept<br /><br />We are now iterating through all <b>accepting</b> configurations of M(x). The existence of a single reachable, accepting configuration is enough to reject the computation.<br /><br />What is wrong with this algorithm? Any space-bounds I am violating? Over-using the power of nondeterminism? Misunderstanding complementation?Daniel Lorchhttps://www.blogger.com/profile/04302402740280438773noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45016770198705169442010-04-15T09:52:20.380-05:002010-04-15T09:52:20.380-05:00M(x) may have different nondeterministic choices, ...M(x) may have different nondeterministic choices, some lead to accept and others leading to reject. In this case both M(x) and N(x) will have (different) choices that lead to acceptance.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90631165967756947672010-04-15T08:56:45.117-05:002010-04-15T08:56:45.117-05:00I am not sure I understand this algorithm. Why can...I am not sure I understand this algorithm. Why can't we just define the following non-deterministic turing machine N(x):<br /><br />1. Non-deterministically guess the accepting configuration of M(x)<br />2. Verify the accepting configuration<br />3. If successful, then reject, otherwise acceptDaniel Lorchhttps://www.blogger.com/profile/04302402740280438773noreply@blogger.com