First post here so hope I'm not missing too many guidelines. I've had this idea for a few weeks now and I can't myself see where I'm going wrong with it, hope it makes some sense to you and thanks in advance for the help. Here we go:
Assuming we could solve a NP-complete problem in logn SPACE, e.g. TSP. Then by reachability we could show that $P = NP$.
The machine will keep track of this information:
- $\log n$ nodes for a path walked, call this memory
pathMem
- $\log n$ nodes for a reconstructed path walked, call this memory
pathMemTemp
- $\log n$ numbers indicating the chosen path, call this
chosenPathNums
- $\log n$ nodes for ending nodes of each path, call this
endMem
some representation of the cost of the walk.
Step 1: Walk $\log n$ steps, note down the $\log n$ walked nodes in pathMem
Step 2: Check that there are no duplicates in pathMem
(that means that you've walked $\log n$ unique nodes).
Step 3: Use a modified version of Savitch that counts the number of possible paths between start node and last node in pathMem
. This should be at most $(\log(n)!)$ paths, represented in that number using binary and we get $O(log(log(n)!))$
Step 4: Find which of these paths that is in pathMem
. Save that number in chosenPathNums
at pos 1.
This gives us a deterministic way of refinding a specific path.
Step 5: Move last node in pathMem
to endMem
pos 1, clear pathMem
.
Step 6: Walk $\log n$ steps from node at endMem
pos 1, note down walked nodes in pathMem
.
Step 7: Check that there are no duplicates in pathMem
(that means that you've walked $\log n$ unique nodes).
Step 8: Reconstruct path that was taken from start node to node at endMem
pos 1 by using Savitch's and the chosenPathNum
, save it in pathMemTemp
.
Step 9: Check that pathMem
and pathMemTemp
has no overlap. If there is overlap, halt with no, otherwise continue.
Step 10: Find the path number that is in pathMem
. Save that number in chosenPathNums
at pos 2.
Step 11: Move last node in pathMem
to endMem
pos 2, clear pathMem
.
Step 12: Rinse and repeat, now checking pathMem
vs start->(endMem
pos 1) and then (endMem
pos 1)->(endMem
pos 2) etc., until you've walked $n$ nodes, thus having $\log n$ nodes in endMem
and $\log n$ numbers in chosenPathNums
.
Step 13: Calculate distance walked, check if less or equal to threshold.
This algorithm could be turned deterministic by looping every possible $\log n$ walk that is found from a node to another node.