VibeMathedMath problems solved with AI
Sign in

The PCP-for-PPAD conjecture of Babichenko, Papadimitriou and Rubinstein (quasilinear form)

End-of-Line is the canonical PPAD-complete problem: given successor and predecessor circuits on {0,1}n\{0,1\}^n with a known source, find another endpoint. A generalized circuit asks for an assignment of values in [0,1][0,1] to wires that ε\varepsilon-satisfies local arithmetic, comparison and Boolean gates. Rubinstein proved PPAD-hardness for constant ε\varepsilon when every gate must be satisfied. Babichenko, Papadimitriou and Rubinstein (2016) conjectured a PCP analogue: are there constants ε,δ>0\varepsilon,\delta>0 and a quasilinear-size reduction from End-of-Line to generalized circuits such that any assignment ε\varepsilon-satisfying all but a δ\delta fraction of gates, wherever the failures lie, yields an End-of-Line solution in polynomial time?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Computational complexity; PPAD and equilibrium computation
Posed by
Yakov Babichenko, Christos Papadimitriou and Aviad Rubinstein, Conjecture 2 of 'Can almost everybody be almost happy?' (ITCS 2016)
Year posed
2016
Years open
10y
Solved
2026-09-25
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Unreviewed
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
32 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: there are fixed rational 0<ε<1/100<\varepsilon<1/10 and 0<δ<10<\delta<1, and deterministic polynomial-time algorithms R,DR,D, such that RR maps an End-of-Line instance of length NN to a generalized circuit of total binary length at most AN⌈log⁡2(N+2)⌉bAN\lceil\log_2(N+2)\rceil^b, every generalized circuit has an acceptable rational assignment of polynomially bounded length, and from any such assignment ε\varepsilon-satisfying all but a δ\delta fraction of gates DD recovers an End-of-Line solution. This also implies the weaker polynomial-size PCP-for-PPAD statement. It does not by itself give new Nash lower bounds; those (Rubinstein, Golowich) still need an exponential-time hypothesis for PPAD.

What the AI did

The release README says the results were produced by an unreleased internal OpenAI model with one fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region, whose write-up was human-edited). The manuscript is authored 'OpenAI' and names no human author.

Verification

No independent mathematician has checked this yet. Checked here: the introduction and Theorem 1.1 were read against Conjecture 2 of Babichenko-Papadimitriou-Rubinstein. lean/docs/136.md does not exist at the pinned commit and formalization.yaml has no entry for this manuscript, so there is no formal statement. The manuscript fixes its own explicit encodings and gate conventions (following Deligkas et al. and Fisher) and handles a normalization of the original End-of-Line definition in a footnote; a reader comparing with the 2016 formulation should check those conventions.

Source

Changelog1 change

Discussion