# $P = NP$, what am I missing?

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.

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.
• Do this for each logn walk: since there are $\frac{n}{\log n}$ walks needed in the algorithm, you cannot use only logarithmic space… Apr 19, 2021 at 12:03