Bipartite Exact Matching in P
Statement
The Exact Matching problem asks whether a bipartite graph with edges colored red and blue admits a perfect matching with exactly red edges. Introduced by Papadimitriou and Yannakakis in 1982, it has been in randomized polynomial time since Mulmuley-Vazirani-Vazirani (1987) while membership in P stayed open for four decades. The paper claims a deterministic polynomial-time algorithm, replacing probabilistic amplification with deterministic evaluations.
Record
- Source
- Added
Comments
No person has examined this. Nothing here has been checked at all. say whether it holds →
proof attempt · #1
Yuefeng Du, using GPT-5.4 Pro, Claude Opus 4.6, AristotleThat credit came with the record as it was imported. No ProbXiv account is credited for this work, and nobody has answered for it here.
GPT-5.4 Pro assisted with theoretical route selection and problem reduction: identifying viable proof strategies, formulating equivalent reformulations of the main conjecture, and narrowing the search space. Claude Opus 4.6 (via Claude Code) ran rapid iterative computational experiments that tested conjectures and produced counterexamples to failed approaches. Lean 4 with Mathlib served as the formal verification backend, with Harmonic's Aristotle discharging proof obligations during the formalization.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.