OpenAI claim summary for CS-174
computer sciencemathematicsTop Open Problemscontributionliterature_reportClaim: literature report
Summary of a claim published in openai/math; not a claim by this platform.
The result supplies the conclusion in this problem with its displayed hypotheses and quantifiers. The broader statements and applications in the manuscript are kept separate from the particular question above. The supporting result is manuscript 1 (family 133; 2026-09-25).
Limitations: The linked openai/math material has not been examined or verified by the platform.
Manuscript
Contents
Complexity of Weisfeiler–Leman graph identification
OpenAI's claim
OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 133; 2026-09-25), the asserted result is that deciding whether supplied-dimension Weisfeiler--Leman refinement identifies a graph is EXPTIME-complete.Mathematical statement of the claimed result
Manuscript 1.
For a finite nonempty simple uncolored undirected graph $G$, let $\operatorname{WLdim}(G)$ be the least dimension of Weisfeiler--Leman refinement that identifies it up to isomorphism among graphs. Dimension one is ordinary neighbor-color refinement; dimensions at least two use the joint replacement-vector rule. The claim is \[ \{(G,k):\operatorname{WLdim}(G)\le k\}\text{ is EXPTIME-complete} \] under deterministic polynomial-time many-one reductions, with adjacency-matrix input and positive integer $k$ encoded in binary.Outline of the argument
For manuscript 1 (family 133; 2026-09-25), binary linear incidence pieces reconstruct every possible equivalent mate by local shifts. Local offsets support a bijective-game strategy, whereas globally compatible offsets give an isomorphism; a computation encoding separates these two conditions to produce the hardness gap.Formal verification
For manuscript 1 (family 133; 2026-09-25), OpenAI lists Lean statements for this assertion: deciding whether supplied-dimension Weisfeiler--Leman refinement identifies a graph is EXPTIME-complete.The selected statement includes the clause used for this problem.
The linked family Comparator checks are ParityLifts.lean, VariableWL.lean, WLIdentification.lean, WeisfeilerLeman.lean.
Their named declarations include OAI.ParityWL.parity_reduction, OAI.VariableWL.main, OAI.WLIdentification.main, OAI.WLTime.unconditional_time_lower_bound.
This site has not executed the Lean code. Described statement coverage is not an independent proof check.
Status caveat
The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.Sources
- OpenAI, The complexity of identifying a graph by Weisfeiler–Leman refinement, 2026-09-25; citation key
OAI:The-complexity-of-identifying-a-graph-by-Weisfeiler-Leman-refinement-September-25-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main. - Family 133: Lean scope.
- Comparator ParityLifts.json.
- Comparator ParityLifts.lean.
- Comparator VariableWL.json.
- Comparator VariableWL.lean.
- Comparator WLIdentification.json.
- Comparator WLIdentification.lean.
- Comparator WeisfeilerLeman.json.
- Comparator WeisfeilerLeman.lean.
- OpenAI catalogue entry.