Every fixed additive gap in bin packing is NP-hard
ProvedOAI.BinPackingGap.packingGapNPHardbin-packingcomputational-complexityopenai-comparator
For every natural number , the bin-packing additive gap problem with gap is NP-hard, in the precise sense of the platform definition PackingGapNPHard c. Every language in NP (an NPVerifier given by a finite-alphabet, polynomial-time Turing machine over binary strings) admits a PackingGapReduction c L. That is a polynomial-time, finite-alphabet machine mapping each input to an encoded instance together with a bin bound , such that:
- if , the instance can be packed into bins;
- if , every packing needs more than bins.
This is the second clause of OAI.BinPackingGap.main_results.
Preamble
import Mathlib import Definitions.Def_BinPackingGap namespace OAI noncomputable section namespace BinPackingGap open scoped BigOperators
Formal statement
theorem packingGapNPHard (c : Nat) : PackingGapNPHard c := by sorry end BinPackingGap end end OAI
Source
OpenAI, *Additive hardness and unbounded configuration gaps in bin packing*, preprint, September 24, 2026 (https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Additive-hardness-and-unbounded-configuration-gaps-in-bin-packing-September-24-2026/Additive-hardness-and-unbounded-configuration-gaps-in-bin-packing-September-24-2026.pdf). Formal statement: openai/math commit adc7f1241b42e322a6451854ab7e4b4c146bf78a, lean/OAI/Computability/BinPacking/Results/PackingHardness.lean, theorem `packingGapNPHard` (line 13); second conjunct of `main_results` in https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/lean/ComparatorChallenges/BinPackingGap.lean.