tag:blogger.com,1999:blog-3722233.post5144286061904945641..comments2021-12-01T13:41:42.544-06:00Comments on Computational Complexity: The Not-So-Simple PathLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-67761279127127815382011-09-01T06:45:45.053-05:002011-09-01T06:45:45.053-05:00Clarifications on my last post:
Statement #5 shou...Clarifications on my last post:<br /><br />Statement #5 should have read: All the shortest available paths are composed of cells marked (x,y), where x+y=a.<br /><br />Statement #6 should have included the condition that all the cells have to be assigned (x,y) coordinates from "s" and "t" before testing the cell "u" to see if it is on a simple path.Jim Blairnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65065690470724137752011-08-31T08:02:10.243-05:002011-08-31T08:02:10.243-05:00I must be missing something.
Why not start a BFS ...I must be missing something.<br /><br />Why not start a BFS at “s” and mark each vertex/cell with its generation. Stop when it reaches “t”. Start a BFS at “t” and mark each cell already marked with a second mark which is its generation relative to t.<br /> <br />Follow any path using cells where s increases by 1 and t decreases by 1.<br /><br />Another way to look at it:<br /><br />1. When you do a BFS, you are creating a counting wave front from the starting cell to every other connected cell.<br /> <br />2. The starting cell is broadcasting its position (RCA) relative to every other cell which can be recorded by every other cell as a shortest distance coordinate x.<br /><br />3. The destination cell then broadcasts its position to every cell assigned an x coordinate and assigns a second coordinate y.<br /><br />4. If the coordinates for “t” are (a,0) then the coordinates for “s” are (0,a).<br /> <br />5. All the shortest available paths have x+y=a.<br /><br />6. Don’t know about all the “simplest paths”, but there is probably a simple triangulation trick that will work to test if a third cell “u” is on a simple path from “s” to “t”.Jim Blairnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39562961261253922502011-08-30T17:04:09.503-05:002011-08-30T17:04:09.503-05:00Wow, I didn't expect the analogy at the end. T...Wow, I didn't expect the analogy at the end. That's pretty brilliant. Thanks!Daniel Aponnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17278964627691170452011-08-27T09:25:43.078-05:002011-08-27T09:25:43.078-05:00I can't say that I have read a lot of papers o...I can't say that I have read a lot of papers or that I am just starting my PhD, but I have seen the following pattern:<br /><br />One would expect as you require an object to have additional properties, it would be easier to find such an object since the number of possible solutions is smaller or equal, given an instance of a problem. <br /><br />However, requiring that the object not only satisfies the usual requirements that identify it as that kind of object (e.g. a path), but that it must also have a certain property, usually seems to blow up the complexity of solving the problem.<br /><br />I find this to be a rule of thumb and I think it relates to proving Deolalikar's proof false, since a complex solution space does not necessarily mean that the problem is hard.Anonymoushttps://www.blogger.com/profile/09364120444779754928noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63714761806563007382011-08-25T08:18:35.466-05:002011-08-25T08:18:35.466-05:00Don't forget that computing shortest simple un...Don't forget that computing shortest simple undirected path is NL-complete!Derrick Stoleehttps://www.blogger.com/profile/08788683962503964865noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7238255074890585772011-08-25T08:09:16.327-05:002011-08-25T08:09:16.327-05:00Thanks for this post! I never really thought about...Thanks for this post! I never really thought about this distinction between paths and simple paths in terms of computational complexity before I asked the question. I realized the importance of it with Ryan's and your answers, and this post makes an even clearer statement about this issue. Thanks then!Brunonoreply@blogger.com