This post was inspired by the simple functions discussion on Bill's post and this question on unique paths.
A path is just a way from getting from point A to point B. A simple path is a path that doesn't cross itself. Some people use "path" to mean simple path and "walk" to mean a general path (like in random walk) but lets not quibble on notation.
To find a path you just keep going until you get there. To follow a simple path you need bread crumbs, some way of remembering where you've been. Often it doesn't matter. There is a path from A to B if and only if there is a simple path. The shortest path from A to B on a graph of positive edge weights is always simple. Ah but it isn't always so simple.
The randomized and deterministic log-space algorithms for undirected connectivity don't give anything close to a simple path. Counting the number of paths is easy, just take powers of the adjacency matrix. Counting the number of simple paths is #P-complete. The longest path is either infinite or easy to find. The longest simple path (Hamiltonian path) is NP-complete. Playing Go with players requiring to follow a simple path (no repeating a board position) is EXP-complete despite being played on a poly-size board. Making paths simple make them much more complex.
In our lives we need the ability to go back, to learn from our mistakes and try other possibilities. There is no where you can go without following a simple path but to follow one requires omniscience and trying to stay on a simple path will limit your choices. Life is not a simple path.
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!
ReplyDeleteDon't forget that computing shortest simple undirected path is NL-complete!
ReplyDeleteI 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:
ReplyDeleteOne 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.
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.
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.
Wow, I didn't expect the analogy at the end. That's pretty brilliant. Thanks!
ReplyDeleteI must be missing something.
ReplyDeleteWhy 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.
Follow any path using cells where s increases by 1 and t decreases by 1.
Another way to look at it:
1. When you do a BFS, you are creating a counting wave front from the starting cell to every other connected cell.
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.
3. The destination cell then broadcasts its position to every cell assigned an x coordinate and assigns a second coordinate y.
4. If the coordinates for “t” are (a,0) then the coordinates for “s” are (0,a).
5. All the shortest available paths have x+y=a.
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”.
Clarifications on my last post:
ReplyDeleteStatement #5 should have read: All the shortest available paths are composed of cells marked (x,y), where x+y=a.
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.