Hacker News Reader

Comment by doormatt | Hacker News Reader

Thanks for the reply! Just to clarify, your proof is relying on the assumption that if an algorithm can be modeled in Algphys, then its execution time in Algphys reflects its true time complexity, right? But can you point to where you prove that modeling a polynomial-time Turing machine in Algphys necessarily results in a polynomial-time trajectory in your framework, across all problem instances? Specifically, how do you rule out the possibility that the mapping itself introduces exponential distortion in some cases?

View on HN

Thanks for the follow-up!

Equivalence of P and Algphys: Section 2.3 and Appendix D show any polynomial-time algorithm can be modeled in Algphys with preserved complexity.

Polynomial Mapping: Section 2.2 and Appendix C detail symplectomorphic reductions, ensuring mappings like those for 3-SAT are polynomial-time computable.

No Exponential Distortion: Appendix F (Elimination of Objections) addresses concerns like exponential precision, confirming mappings don’t inflate complexity for polynomial algorithms.

The exponential bounds come from the inherent structure of NP-complete problems, not the mapping itself.

You mention that Algphys can simulate any polynomial-time Turing algorithm with preserved complexity, but in your construction, the dynamics of Algphys are governed by physical properties: gradient norms, Hessian spectra, rigidity, etc. How do you guarantee that these geometric constraints don’t impose an exponential slowdown on some Turing algorithms that would otherwise run in polynomial time? Specifically, where do you prove that no such algorithm is mapped into a high-rigidity trajectory with exponential execution time?

You’re right — the paper does not currently contain an explicit theorem stating, word-for-word, that “every polynomial-time Turing machine is mapped to a low-rigidity region.”

In section C.4, at the end of step 4, there is a statement: the Hessian spectrum creates obstacles for polynomial algorithms in certain places, which can be interpreted as areas of high rigidity. However, it does not explicitly state that algorithms never enter these areas, but only highlights their difficulties. I agree that this is not written down as the only explicit lemma of the form you asked for.

I can add an explicit lemma to the appendix, which will specify in the required form the property that polynomial-time algorithms never fall into areas with high rigidity, and I will update the preprint. Meanwhile, the existing material (Thm. 2.5, Thms. C.1/C.4, App. F.4, Thm. E.1) contains ingredients that substantiate the claim; the new lemma will make this reference explicit.

If you want, I can update the preprint soon and report back with the precise lemma number and page.

Thanks so much for being so open and willing to discuss this!

Just to be clear though, if that lemma isn’t yet explicitly proven, then the core claim (that Algphys cannot simulate certain NP-complete solutions in polynomial time) has not been established. I agree the components may suggest difficulty in high-rigidity regions, but unless you formally prove that no polynomial-time Turing machine’s trajectory enters those regions, the P != NP conclusion doesn’t follow.

Thanks for the help! It will take at least a week to fix the gap. During the addition, I came across a more serious problem: there was a contradiction between the "hard" function (ε = 2^(—n)) and the statement Algphys ⊆ P. I'm dealing with this now, and I'll need additional verification.

Reply on news.ycombinator.com