A polynomial-time absolute-additive bin-packing algorithm implies P = NP
OpenOAI.BinPackingGap.pEqualsNP_of_exists_absoluteAdditiveAlgorithmbin-packingcomputational-complexityopenai-comparator
If for some constant there is an absolute additive algorithm with error , then . Such an algorithm is a finite-alphabet Turing machine computable in polynomial time on binary encodings, which on every valid encoded instance outputs a feasible packing using at most bins (AbsoluteAdditiveAlgorithm c). Here P = NP is PEqualsNP, equality of the platform's classes ClassP and ClassNP of bit languages.
This is the forward direction of the third 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 pEqualsNP_of_exists_absoluteAdditiveAlgorithm
(h : ∃ c : Nat, Nonempty (AbsoluteAdditiveAlgorithm c)) : PEqualsNP := 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/AdditiveHardness.lean, theorem `pEqualsNP_of_exists_absoluteAdditiveAlgorithm` (line 12); forward direction of the third conjunct of `main_results` in https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/lean/ComparatorChallenges/BinPackingGap.lean.