Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A polynomial-time absolute-additive bin-packing algorithm implies P = NP

Open
OAI.BinPackingGap.pEqualsNP_of_exists_absoluteAdditiveAlgorithm

by SamenHossain · Oct 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

bin-packingcomputational-complexityopenai-comparator

If for some constant ccc there is an absolute additive algorithm with error ccc, then P=NP\mathrm P=\mathrm{NP}P=NP. 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 OPT+c\mathrm{OPT}+cOPT+c 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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me