{"id":"arxiv/2606.03194","url":"https://arxiv.org/abs/2606.03194","tags":["cs.CC","math.CO","math.OC"],"score":0,"title":"Lean 4 Machine-Verified Proof of P = NP via the Pedigree Polytope Membership Problem","domain":"cs.CC","source":"arxiv","authors":["T. S. Arthanari"],"reviews":0,"subject":"cs.CC","summary":"The Membership Problem for Pedigree Polytope (M3P) asks, given $X\\in\\mathbb{Q}^{\\binom{n}{3}}$, whether $X\\in\\mathrm{conv}(P_n)$, where $P_n$ is the set of all pedigrees. A pedigree is a structured encoding of a Hamiltonian cycle construction in $K_n$. We establish that M3P is solvable in strongly polynomial time via a recursively constructed layered network $(N_k, R_k, μ)$ and a multicommodity flow problem MCF$(k)$. The necessary and sufficient condition for membership established is that the optimal total flow in MCF$(n-1)$ equals the maximum possible flow $z_{\\max}$. The complexity…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-02","reactions":{}}