Wolfram Physics Q&A

One very exciting side effect of our formalism is the ability to recast many open questions in theoretical computer science and computational complexity theory in terms of it; as an illustrative example of this, note that the P vs. NP problem can, at some level, be thought of as corresponding to a question about the relative rates of divergence and convergence of branch pairs in the multiway evolution graph for our universe.

More precisely, we begin by noting that Turing machines compute by following a single multiway branch in a completely deterministic fashion. Nondeterministic Turing machines, on the other hand, compute by also following a single multiway branch, but with the choices of which successive branches to take made in accordance with some nondeterministic rule. Therefore, P vs. NP (i.e. the question of whether the set of all problems solvable in polynomial time by a deterministic Turing machine is identical to the set of problems solvable in polynomial time by a nondeterministic Turing machine) is ultimately a question about whether a multiway state obtained by following a predetermined path in the multiway system is always reachable by following a nondeterministic path of approximately the same length. This is trivially true in the case of highly causal-invariant universes (e.g. ones in which all multiway branches eventually converge to a normal form). For a more nontrivial, non-terminating multiway system, the relative rates of branch pair divergence/convergence place constraints on the degree to which P and NP can be related.