1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

It is not clear what is your question, but I will guess that it is "what is my mistake in my proof of $P = NP$?"

In addition to the fact that the algorithm does not guarantee to find the minimal path (because the algorithm cant deterministicaly choose the endMem nodes), the number of possible $\log n$-walks given $\log n$ nodes is not polynomial: $(\log n)! \sim \left(\frac{\log n}{e}\right)^{\log n}\sqrt{2\pi\log n}\sim \frac{\sqrt{2\pi\log n}}{n}e^{\log n \log \log n}\sim \sqrt{2\pi\log n}\times n^{\log\log n - 1}$.

As for the space complexity, to check there are no overlap between two $\log n$-walks, you need to keep track of the whole path (and not only two consecutive $\log n$-walks). That needs $\Omega(n\log n)$ space ($n$ nodes with a binary encoding of size $\log n$). So the corresponding Turing Machine use polynomial space, not logarithmic space.

$\endgroup$
5
  • $\begingroup$ Thanks for your answer, that was also my exact question, though I have some follow up. First, do I really need to deterministically choose endMem nodes? Using an NTM together with reachability should be enough to show that TSP is in P if it can be solved in logn SPACE. Or did I misinterpret this? Then, yes, that's the number of logn possible walks, but by representing them as regular binary format, shouldn't it bring it to logn(sqrt(2*pi*logn) * n^(log(logn-1)))? This might be a complete misinterpretation on my side though... $\endgroup$ – Simon Apr 19 at 10:57
  • $\begingroup$ I edited my answer concerning the space complexity. $\endgroup$ – Nathaniel Apr 19 at 11:11
  • $\begingroup$ If you keep track of the start point, the end point, and then the number specifying the valid path among the set of valid path. Do this for each logn walk, then you would be able to generate every logn walk, from three values, thus being able to check a new logn walk against all other logn walks, without needing to keep track of n nodes. Therefore being able to stay within logn SPACE $\endgroup$ – Simon Apr 19 at 11:43
  • 1
    $\begingroup$ Do this for each logn walk: since there are $\frac{n}{\log n}$ walks needed in the algorithm, you cannot use only logarithmic space… $\endgroup$ – Nathaniel Apr 19 at 12:03
  • $\begingroup$ Ah, that's correct! Thank you so much for the help! $\endgroup$ – Simon Apr 19 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.