Bin packing within an additive constant: is there a polynomial-time algorithm using at most OPT + C bins?
Bin packing is NP-hard and admits no multiplicative ratio below unless P = NP, but its asymptotic behaviour is much better: Fernandez de la Vega and Lueker gave an asymptotic scheme, Karmarkar and Karp (1982) an algorithm using bins, Rothvoss and Hoberg and Rothvoss . No hardness of any additive form was known, so even an algorithm was not excluded. Williamson and Shmoys list the question among the open problems of their 2011 book (Chapter 17, Problem 3). Is there a deterministic polynomial-time algorithm that, for some absolute constant , packs every instance into at most bins?
- Result
- Disproved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Construction
- Field
- Approximation algorithms; hardness of bin packing
- Posed by
- David P. Williamson and David B. Shmoys (listed open problem), in the line of Karmarkar and Karp's additive algorithm
- Year posed
- 2011
- Years open
- 15y
- Solved
- 2026-09-24
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Lean-checked, statement unaudited
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version adc7f12
- Significance
- 45 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.2: for every fixed integer it is NP-hard to distinguish pairs where packs into bins from pairs where needs more than bins, with rational sizes all greater than . Corollary 1.3: a deterministic polynomial-time algorithm using at most bins for an absolute constant exists if and only if P = NP. The reduction goes from vertex cover with Håstad's gap through a competing two-tree interval construction encoded in five-item bins. Not shown: a lower bound of order matching Hoberg-Rothvoss, or hardness for a fixed number of item sizes (polynomial by Goemans-Rothvoss).
What the AI did
The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. 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 manuscripts are authored 'OpenAI' and name no human author. The family is a single manuscript, 'Additive hardness and unbounded configuration gaps in bin packing' (September 24, 2026); the same reduction also disproves the Modified Integer Round-Up Conjecture, entered separately.
Verification
No independent mathematician has checked this yet. Checked here: Theorem 1.2 and Corollary 1.3 were read against the question as Williamson and Shmoys pose it. Theorem 1.2 makes distinguishing bins from more than bins NP-hard for each fixed , with sizes above ; Corollary 1.3 says an algorithm exists if and only if P = NP. The answer is negative unless P = NP, the standard form of a complete answer to such a question; solveType disproved is recorded on that understanding. Lean: the same formalised declaration OAI.BinPackingGap.main_results (listed in formalization.yaml) was read here; its second and third conjuncts state PackingGapNPHard c for every c (polynomial-time reductions from every NP language with completeness and soundness) and that an absolute additive algorithm exists iff P = NP, with P, NP and polynomial time defined on Mathlib's TM2 machines. That states the headline. Not rebuilt here; the hand-built complexity definitions were read but not audited.