OAI.VariableWL.general_hard: intermediate lemma from OpenAI, Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphs

Proved

OAI.VariableWL.general_hard

by dbenbenn · Oct 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

openai-math

An intermediate lemma of the split of OpenAI's proof of OAI.VariableWL.main, carved from OpenAI's openai/math development for this platform. The statement and its proof are OpenAI's (OpenAI, Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphs, OpenAI Math Release, September 25, 2026, result family 133, github.com/openai/math, Apache License 2.0); in Lean it is the declaration OAI.VariableWL.general_hard of lean/OAI/Combinatorics/VariableWL/Completeness.lean at commit adc7f12, ported to Lean 4.33.1 and Mathlib 0df444a.

The statement, as published (namespace OAI.VariableWL):

 theorem general_hard : ∀R : Language, InEXPTIME R → PolytimeReduces R WL

Definitions. The statement is written with OAI.VariableWL.InEXPTIME, OAI.VariableWL.Language, OAI.VariableWL.PolytimeReduces and OAI.VariableWL.WL (the published bundle Def_VariableWL).

Used by. The proof of OAI.VariableWL.main of this split imports it.

Preamble

import Mathlib
import Definitions.Def_VariableWL

Formal statement

section

set_option linter.all false
set_option linter.unusedVariables false
set_option linter.unusedTactic false
set_option linter.unreachableTactic false

namespace OAI

universe uVariable1 uVariable2

namespace VariableWL
 theorem general_hard : ∀R : Language, InEXPTIME R → PolytimeReduces R WL := by
  sorry
end VariableWL

end OAI
end

Source

OpenAI, Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphs, OpenAI Math Release, September 25, 2026, https://github.com/openai/math (result family 133; paper: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Variable-dimension-Weisfeiler-Leman-equivalence-on-general-and-subcubic-graphs-September-25-2026/paper.pdf; Apache License 2.0); Lean: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/lean/OAI/Combinatorics/VariableWL/Completeness.lean (declaration OAI.VariableWL.general_hard)

View graph