P = NP Is Not About Stacking Paths

An NTM computation offers a tempting picture. At every step, the machine chooses one of several moves. A deterministic machine could record those choices, run the chosen path, return to the start, and try the next one.

That picture is correct. It is also not a proof that $\mathrm{P}=\mathrm{NP}$.

The obvious simulation works

Suppose the computation has depth $p(n)$ and, for simplicity, each configuration has two successors. A path can be recorded as a binary word

$$\pi =(b_1,b_2,\dots ,b_{p(n)})\in \{0,1{\}}^{p(n)}.$$

The deterministic simulator can treat $\pi$ as a counter. It simulates the branch described by $\pi$, resets, increments the counter, and continues. If one path accepts, it accepts; if none does, it rejects.

The path index is small. It has only $p(n)$ bits, so storing it is polynomial-space work. The problem is not remembering which path to try.

The tree charges once per path

The problem is the number of paths. With branching factor $b$ and depth $p(n)$, the tree can contain up to

$$b^{p(n)}=2^{O(p(n))}$$

leaves. If simulating one path takes polynomial time, exhaustive enumeration takes

$$T_{\mathrm{enum}}(n)=O\left(p(n)b^{p(n)}\right)=2^{O(p(n))}.$$

Resetting and backtracking save space because the simulator stores only a path, a counter, and a current configuration. They do not save the time spent on the other paths. Serialising a wide tree into a list changes the order of the work, not its amount.

Where the real question begins

For a language in P, there exists a polynomial-time deterministic machine whose computation is a single path. For a language in NP, there exists a polynomial-depth nondeterministic tree whose accepting path can be found existentially.

The naive deterministic simulation turns that tree into an exponentially long list. That proves that NP computations can be simulated deterministically in exponential time, and in polynomial space. It does not show that they can be simulated in polynomial time.

So the open question is not whether we can walk back and try another path. We can. The question is whether a deterministic algorithm can avoid paying for almost all of the paths by discovering structure, sharing subcomputations, or pruning large parts of the tree.

$\mathrm{P}=\mathrm{NP}$ would mean that such a shortcut always exists. It is not about stacking paths for free; it is about finding a way not to stack them at all.