Derandomization of logarithmic space: is L = RL = BPL?
is the class of languages decided in deterministic logarithmic space. allows a polynomial-time logarithmic-space machine fresh random bits with one-sided error (acceptance probability on no-inputs, at least on yes-inputs), and allows two-sided bounded error ( versus ). Aleliunas, Karp, Lipton, Lovasz and Rackoff, after giving a randomized logspace algorithm for undirected connectivity, asked whether polynomial-time randomized logarithmic space can be simulated in deterministic logarithmic space. The best unconditional results before this work were Saks-Zhou space , improved by Hoza to , and Nisan's simultaneous polynomial time with space. Is ?
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Space-bounded derandomization
- Posed by
- R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovasz and C. Rackoff (1979)
- Year posed
- 1979
- Years open
- 47y
- Solved
- 2026-09-23
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Lean-checked, statement unaudited
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version fd4aeeb
- Significance
- 65 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Claims : every language decided with bounded one-sided or two-sided error by a randomized machine with polynomial worst-case running time and space is decided by a deterministic -space machine. Quantitatively, acceptance probabilities can be approximated to within in space and time . The method builds a hierarchy of copies of the configuration graph with a shared finite random environment and evaluates a family of -bit estimators, more than three quarters of them accurate, by exhaustive enumeration. It does not give a pseudorandom generator with logarithmic seed, and it does not address randomized logspace without a polynomial time bound.
What the AI did
The release README says the manuscripts were produced by an unreleased internal OpenAI model, which was posed some 4,000 open research problems during an evaluation, with the vast majority of results obtained by one fixed procedure averaging about three hours of ChatGPT Pro thinking compute each. This manuscript is not among the README's named exceptions. It is credited to OpenAI with no human author named.
Verification
No independent mathematician has checked this yet. Theorem 1.1 was read against the posed question and states the full equality L = RL = BPL for the standard model (polynomial worst-case running time on every random tape, logarithmic space counting all live counters). Lean-checked on the release's Comparator challenge LogspaceEquality (declaration OAI.ExactDerandomization.exact_logarithmic_space_derandomization, solution module OAI.Computability.Logspace.Equality), added in the 7 October 2026 update and listed in lean/formalization.yaml. Its statement was read here: for finite transition-table machines over binary words, with read-only input heads, binary work tapes, one coin bit per step and space at most on every coin tape, the classes L, RL (polynomial clock, versus ) and BPL ( versus ) satisfy L = RL and RL = BPL. That is the headline. Not rebuilt here. The paper's quantitative approximation ( accuracy in space ) and its explicit compiler are not part of the Comparator statement. The paper concerns polynomial-time randomized logspace; it does not claim that randomized logspace machines without a time bound are derandomized.