Reproduce “Lean 4 Machine-Verified Proof of P = NP via the Pedigree Polytope Membership Problem” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

T.S. Arthanari

This work proposes a resolution to the P vs. NP problem by establishing that the Membership Problem for Pedigree Polytope (M3P) is solvable in strongly polynomial time, implying that the NP-complete Symmetric Travelling Salesman Problem (STSP) is in P. The entire logical proof chain for P=NP has been formally machine-verified using the Lean 4 proof assistant.

Key insights

  • The membership problem for the pedigree polytope (M3P) can be solved in strongly polynomial time, specifically O(n^14) arithmetic steps, by leveraging properties of combinatorial linear programs and Tardos's algorithm.
  • A necessary and sufficient condition for a vector's membership in the pedigree polytope is established through the feasibility of a multicommodity flow problem, whose optimal flow must match a maximum possible flow.
  • Applying established polyhedral theory (Maurras, Grötschel, Lovász, Schrijver), a polynomial-time membership oracle for the pedigree polytope implies polynomial-time linear optimization over it.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.