Proves \(\mathsf L=\mathsf{RL}=\mathsf{BPL}\), resolving derandomization for bounded-error logarithmic-space computation. An effective compiler converts each randomized polynomial-time logarithmic-space machine deciding a language with one-sided or two-sided error into a deterministic logarithmic-space decider with explicit polynomial running-time bounds. (OpenAI’s Lean note)
Lean is a language for mathematical statements and proofs that a computer can verify. The assessments below ask whether those statements express the result OpenAI describes here.
The two independent assessments disagree on how much of the result described above is expressed by the Lean statements. Read the assessments
One problem has been reported by others; the atlas has not judged it.
In Exact derandomization of logarithmic space: L = RL = BPL, 23 September 2026
The paper’s main theorem is shown as a possible match to OpenAI’s description. No review confirming the selection is recorded.
No Lean statement in the release is paired with this theorem.
In Exact derandomization of logarithmic space: L = RL = BPL, 23 September 2026
Possible match to OpenAI’s description, selected because it shares the most wording. No review confirming the selection is recorded.
Fix a randomized machine \mathcal M with polynomial worst-case running time and O(\log(n+2)) work space. Let p_{\mathcal M}(x) be its acceptance probability on an input x of length n. There is a uniform deterministic algorithm which, on input (x,1^q) with q\ge1, outputs an integer 0\le a\le2^{q+2} satisfying
It uses O(\log(n+2)+q) work space and (n+2)^{O(1)}2^{O(q)} time. The constants depend only on \mathcal M.
The release does not say which paper theorem its catalogue describes. Both statements above are shown whole: the paper’s main theorem first, then the statement that shares the most wording with the description. The atlas has not reviewed either choice.
Each paper opens as a reading page in the browser, with the PDF beside it. The statements each paper opens with are on its reading page.
Lean is a language for mathematical statements and proofs that a computer can verify. The Lean statement below is shown beside its possible paper counterpart, with the reason they were linked.
For a configured theorem, the Comparator program tests whether OpenAI’s separate proof proves the exact Lean statement using only the allowed axioms. Some statement files instead configure definitions for comparison by name and type. Acceptance does not establish that a formal statement means the same thing as the paper’s theorem.
LogspaceEqualityThe paper states
In Exact derandomization of logarithmic space: L = RL = BPL, 23 September 2026
Fix a randomized machine \mathcal M with polynomial worst-case running time and O(\log(n+2)) work space. Let p_{\mathcal M}(x) be its acceptance probability on an input x of length n. There is a uniform deterministic algorithm which, on input (x,1^q) with q\ge1, outputs an integer 0\le a\le2^{q+2} satisfying
It uses O(\log(n+2)+q) work space and (n+2)^{O(1)}2^{O(q)} time. The constants depend only on \mathcal M.
The words they share: acceptance, deterministic, machine, polynomial, probability, randomized, running, space, time.
Possible Lean counterpart
Selected from shared wording. No review of whether the statements mean the same thing is recorded.
LogspaceEquality.lean, the release lists it as a main result.
theorem exact_logarithmic_space_derandomization : L = RL ∧ RL = BPL := by sorryThis file states the theorem with sorry, a placeholder, in place of its proof. OpenAI supplies a separate proof file. Comparator tests whether that proof proves the statement here.
20 definitions are compared by name and type only: Word, Language, CoinTape, move, moveInput, readInput and 14 more.
three independent groups report that Comparator accepted runs for this Lean statement file: cert-machine; MathVet; Neal McBurnett, openai-math-lean-tooling. Who ran the proof-verification program
MathVet and cert-machine disagree on how much of the advertised result the Lean statements express. MathVet finds that the Lean statements express or imply the whole advertised result (their term: “full”); cert-machine finds that the Lean statements express a narrower statement than the advertised result (their term: “NARROWER — DECLARED”).
MathVet and Carlos Toledo’s cert-machine independently assessed whether this family’s Lean statements express the whole result OpenAI describes in its catalogue. These are assessments of the family as a whole, not of each paper theorem separately.
MathVet finds that the Lean statements express or imply the whole advertised result (their term: “full”).
Their note: Lean states L = RL ∧ RL = BPL for binary languages in an explicit multi-head, multi-tape logspace Turing-machine model (one fresh coin per step, polynomial clock on every coin tape, RL = 0 / >= 1/2, BPL = <= 1/3 / >= 2/3), which is the paper’s Theorem after unfolding L, RL, BPL and chaining the two equalities; the binary-alphabet convention is the only routine step. The summary’s second sentence (effective compiler with explicit polynomial running-time bounds,) has no Lean statement, as the scope note says.
Definitions the group asks readers to compare with the paper: Word / Language: languages are sets of binary words (List Bool) only; the paper does not fix the alphabet in its Section 1, so the reduction from larger alphabets is a routine encoding step, not a restriction on the class.; Machine / Action / Configuration: finite transition-table machine with q+1 states, w two-way-infinite binary work tapes (blank = false) and h read-only two-way input heads, with q, w, h chosen existentially; standard, and matches the paper’s 'finite control, endmarked read-only input, finitely many work tapes’ model.; Machine.step / run: one fresh coin bit per step (coins t used at step t+1), halting states are fixed points; matches 'fresh independent fair bits’ and cannot reuse a past coin except via finite control.; Machine.LogSpace: space = number of distinct cells visited by each work head up to time t, summed over tapes, bounded by c * Nat.clog 2 (|x|+2) for every input, every coin tape and every time t; standard counted-cell convention (blank-cell visits count), same as the paper.; Machine.Decides: for every x some time t with all coin tapes halted with output b and (b = true <-> x in A); no explicit time bound is imposed on L-machines (polynomial time follows from the configuration count, as the paper notes); standard.; Machine.HaltsBy: halting by the clock on EVERY coin tape (worst-case time), as the paper requires (‘All randomized running-time bounds hold on every random tape’); standard.; Machine.acceptanceProbability: exact fraction of the 2^t coin strings of length t (padded with false) whose time-t state outputs true, with t = polynomialClock c k |x| = c*(|x|+2)^k; standard.; RL / BPL: thresholds are exactly 0 on no and >= 1/2 on yes (RL), <= 1/3 on no and >= 2/3 on yes (BPL), as; standard.
“full”, in their words: The challenge statements imply the headline claim after unpacking definitions or one routine step.
Their method: An independent, model-assisted, pre-referee reading of each family’s challenge statements against its headline claim under a published rubric (PROTOCOL.md), with its own Comparator runs per challenge.
cert-machine finds that the Lean statements express a narrower statement than the advertised result (their term: “NARROWER — DECLARED”).
The gap they name: The effective compiler and its explicit polynomial running-time bounds (headline’s second sentence) are not stated; only the class equality is.
“NARROWER — DECLARED”, in their words: The challenge statements state less than the headline, and OpenAI’s Lean note says so.
Their method: Every Comparator challenge re-run on Linux with nanoda switched on, decided by a preregistered rule.
OpenAI’s own note on what its Lean covers
The formalization proves $\mathsf L=\mathsf{RL}=\mathsf{BPL}$ for binary languages in an explicit Turing-machine model with logarithmic workspace. The randomized classes use polynomial time: $\mathsf{RL}$ never accepts a no-instance and accepts a yes-instance with probability at least $1/2$, while $\mathsf{BPL}$ has acceptance probability at least $2/3$ on yes-instances and at most $1/3$ on no-instances. Thus bounded-error randomness does not enlarge deterministic logarithmic space in this model.
The selected theorem asserts equality of the language classes. The paper’s explicit compiler and numerical running-time bounds are not separately stated in this Comparator target.
Exact equality of deterministic and randomized logarithmic space LogspaceEquality
Unreviewed AI draft: states a paper’s theorem as the paper does. States the main theorem L = RL = BPL in an explicit machine model. Comparator treats twenty of the file’s definitions as holes filled from OpenAI’s library; eighteen of them, including L, RL and BPL, have library bodies matching the challenge file after whitespace normalisation, and the two head-movement helpers were not compared.
These groups report running Comparator with the release’s Lean statement files. For a configured theorem, it verifies OpenAI’s separate proof against the exact statement; some files instead configure definitions for comparison by name and type. Each row is the named group’s report. Atlas has not repeated the runs.
These reports do not list the software versions, proof-verification programs, axioms, time or memory in separate fields. Any such details in a report’s prose are reproduced below.
LogspaceEqualityThree reports, all at the release’s recorded version.
| Reported by | Their word | Their account | Date | Original report |
|---|---|---|---|---|
| cert-machine | “CERTIFIED” | Re-run through Comparator with the independent nanoda kernel switched on: Lean’s kernel and nanoda both accept OpenAI’s solution. | 10 October 2026 | Original report |
| MathVet | “comparator-sandboxed-pass” | Re-run through Comparator in a sandboxed virtual machine: accepted. | 10 October 2026 | Original report |
| Neal McBurnett, openai-math-lean-tooling | “accepted” | Re-run through Comparator with Lean’s kernel: accepted (the check took 348 s; peak memory 6.5 GiB). | 11 October 2026 | Original report |
Other people’s accounts of running proof-verification software, with links to their reports.
Jack McCarthy, Re-running Comparator with the definition holes pinned, 9 October 2026. Source
With the definition holes pinned so the solver’s definitions must match the challenge, Comparator reports the solution is okay for this challenge, so the hole was not being abused by OpenAI’s own solution.
Jack McCarthy, OpenAI math: Comparator fixes (mirror of openai/math at fd4aeeb), 9 October 2026. Source
With all 20 definition holes removed from the configuration, so that Comparator compares the definition bodies too, the release’s solution still passes; run with the Lean kernel only, on macOS without Comparator’s sandbox.
Lean community, OpenAI releases solutions to hundreds of problems (117 messages, 6-10 Oct 2026), 6 October 2026. Source
Jack McCarthy re-ran Comparator on Brenier, EuclideanFiveColor, KServer, LogspaceEquality, Naimark and Rokhlin with definition_names removed and all report the solution okay (Lean kernel only, macOS, no sandbox).
Reports of errors and corrections from outside readers, as they state them. The atlas has not judged them.
Alex Meiburg, Several of the comparator challenges in the OpenAI release are broken and hackable, 8 October 2026. Source
Reported as broken in the same way: its machine definitions are listed as holes, so a trivial replacement makes the checked statement vacuous.
These links come from the papers’ bibliographies. A citation records that one paper cites another; how each cited result is used has not been examined here.
This family’s papers cite no paper elsewhere in the release.
No paper elsewhere in the release cites this family’s papers.
Each paper’s outside references are listed with it on its reading page, where each citation is placed. Every outside work cited in the release: References outside the release
Atlas has no contributed explanation for this family yet. You can offer one with a GitHub account. You receive named credit and disclose any AI assistance.
Each button opens a GitHub form with this page and its source version filled in. Opening the form does not reserve the work.
Offer to write an explanationCompare the Lean statement with the paperSuggest a source attributionSuggest a change
Commentary on this family by others, dated and credited. It is commentary, not a finding.
An unsigned public tier list, the OpenAI Math Tier List, classes it as a proof and rates its significance, if it holds up, as “Would win a Fields Medal”. The page says that nothing on it is verified.
Author not stated. Source
Scientific American (byline not recorded), The most exciting claims from OpenAI’s heap of new proofs, 8 October 2026. Source
Ran Raz (Princeton) says there were strong reasons to believe L = RL but they saw no promising direction before this proof.
From scottaaronson.blog, 7 October 2026. Source
Aaronson counts L = BPL among the great derandomization conjectures short of P = BPP, whose truth was never seriously doubted but on which a whole subcommunity worked.
Each item identifies a statement, definition or report that needs further review. Its link opens a GitHub form with the source version already recorded.
Word, Language, CoinTape, move, moveInput, readInput, initial, step and 12 more Open the formWhy this passage is shown
Theorem 1.1 (Exact logarithmic-space derandomization)
In Exact derandomization of logarithmic space, 23 September 2026
Why this passage is shown
Theorem 1.2 (Acceptance-probability approximation)
In Exact derandomization of logarithmic space, 23 September 2026
Independent assessment
MathVet
14c7f91Independent assessment
Carlos Toledo’s cert-machine
9814e4cProof-verification report
cert-machine, LogspaceEquality
Proof-verification report
MathVet, LogspaceEquality
Proof-verification report
Neal McBurnett, openai-math-lean-tooling, LogspaceEquality
Lean statement
LogspaceEquality