Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

If P = NP, bin packing has an exact polynomial-time algorithm on binary encodings

Open
OAI.BinPackingGap.exists_optimal_algorithm_of_pEqualsNP

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

bin-packingcomputational-complexityopenai-comparator

Assume P=NP\mathrm P=\mathrm{NP}P=NP (PEqualsNP). Then there is an absolute additive algorithm with error 000: a finite-alphabet, polynomial-time Turing machine on binary strings with the following behaviour.

  1. On the encoding of every valid raw instance (a list of rational sizes in (0,1](0,1](0,1]), it outputs a feasible packing whose number of bins equals the optimum OPT\mathrm{OPT}OPT.
  2. On the encoding of the empty instance, it outputs the empty packing ⟨0,[ ]⟩\langle 0,[\,]\rangle⟨0,[]⟩.
  3. On every input that does not decode to a raw instance, it outputs none.
  4. On the encoding of every invalid raw instance, it outputs none.

This is the fourth clause of OAI.BinPackingGap.main_results. It also gives the backward direction of the third clause, with c=0c=0c=0.

Preamble
import Mathlib
import Definitions.Def_BinPackingGap

namespace OAI

noncomputable section

namespace BinPackingGap

open scoped BigOperators
Formal statement
theorem exists_optimal_algorithm_of_pEqualsNP :
    PEqualsNP → ∃ algorithm : AbsoluteAdditiveAlgorithm 0,
    (∀ (items : RawInstance) (valid : items.Valid), ∃ packing : RawPacking,
      algorithm.run (BinaryEncoding.rawInstanceBits items) = some packing ∧
      packing.Feasible items ∧ packing.bins = opt (items.toInstance valid)) ∧
    algorithm.run (BinaryEncoding.rawInstanceBits []) = some ⟨0, []⟩ ∧
    (∀ input : List Bool, BinaryEncoding.decodeRawInstance input = none →
      algorithm.run input = none) ∧
    (∀ items : RawInstance, ¬ items.Valid →
      algorithm.run (BinaryEncoding.rawInstanceBits items) = none) := 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/OptimalSearch.lean, definition `absoluteAdditiveAlgorithm_of_pEqualsNP` with the theorems `absoluteAdditiveAlgorithm_of_pEqualsNP_optimal`, `_empty`, `_malformed` and `_invalid`, combined exactly as in the fourth 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