Models CLI now auto-generates test cases and an evaluator (github.blog)

I know how this sounds — it’s one of the hardest and most debated problems in CS, and many have tried and failed. I don’t claim to have the final answer, but I believe the approach I used might at least offer some fresh perspective or provoke useful critique.

The idea involves geometric separation between deterministic and nondeterministic computation, using high-dimensional lattice constructions and some physics-inspired intuition. The full argument is technical, but I tried to keep it logically structured.

The preprint is 93 pages long. It was originally written in Russian, and I created an English version via machine translation, so apologies in advance for awkward wording or formatting.

DOI and full paper (both languages): https://doi.org/10.5281/zenodo.16759468

I’m genuinely open to feedback — whether it’s pointing out flaws, questioning assumptions, or just explaining why this approach doesn’t work. Any form of critical input is welcome.

If there’s interest, I can also create a short video explanation in simple terms to walk through the core ideas — even though I don’t have a channel or any audience yet.

Thanks in advance for taking the time, even if it’s just to skim or tell me what to fix!

Comments (5)

doormatt · 2h ago

Just to clarify, how exactly does proving exponential lower bounds for Algphys translate into a proof that no polynomial time algorithm exists for NP-complete problems in the standard Turing model?

Isn’t it possible that your "hard" instances could be solvable in polynomial time by some algorithm that doesn’t rely on geometric modeling or Hamiltonian dynamics?

How do you justify that every polynomial-time Turing machine algorithm can be modeled as a trajectory in your Hamiltonian system?

LaghZen · 2h ago

Hi! Thanks for the question!

1. Algphys is shown to be equivalent to P, meaning any polynomial-time Turing algorithm can be modeled in Algphys. The paper constructs "frustrated" 3-SAT instances requiring exponential time in Algphys due to high combinatorial complexity and spectral properties (e.g., Hessian eigenvalues growing as ~ 2^n). Since Algphys = P, this implies no polynomial-time Turing algorithm can solve NP-complete problems.

2. The equivalence of Algphys and P means any polynomial-time algorithm, regardless of approach, can be modeled in Algphys. The exponential lower bound for these instances in Algphys applies to all polynomial-time Turing algorithms, suggesting these "hard" instances are inherently exponential, no matter the method.

3. The paper establishes P ~ Algphys by mapping Turing machine states to points on a symplectic manifold, with the cost function H encoding computation steps. The Hamiltonian dynamics (γ̇(t) = J∇H(γ(t))) simulate the algorithm’s execution path, ensuring every polynomial-time algorithm corresponds to a trajectory in Algphys.

doormatt · 2h ago

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?

LaghZen · 1h ago

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.

doormatt · 19m ago

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?