VibeMathedMath problems solved with AI
Sign in

Derandomization of logarithmic space: is L = RL = BPL?

L\mathsf L is the class of languages decided in deterministic logarithmic space. RL\mathsf{RL} allows a polynomial-time logarithmic-space machine fresh random bits with one-sided error (acceptance probability 00 on no-inputs, at least 1/21/2 on yes-inputs), and BPL\mathsf{BPL} allows two-sided bounded error (≤1/3\le1/3 versus ≥2/3\ge2/3). 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 O(log⁡3/2n)O(\log^{3/2}n), improved by Hoza to O(log⁡3/2n/log⁡log⁡n)O(\log^{3/2}n/\sqrt{\log\log n}), and Nisan's simultaneous polynomial time with O(log⁡2n)O(\log^2n) space. Is L=RL=BPL\mathsf L=\mathsf{RL}=\mathsf{BPL}?

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
Unreviewed
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
65 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Claims L=RL=BPL\mathsf L=\mathsf{RL}=\mathsf{BPL}: every language decided with bounded one-sided or two-sided error by a randomized machine with polynomial worst-case running time and O(log⁡n)O(\log n) space is decided by a deterministic O(log⁡n)O(\log n)-space machine. Quantitatively, acceptance probabilities can be approximated to within 2−q2^{-q} in space O(log⁡(n+2)+q)O(\log(n+2)+q) and time (n+2)O(1)2O(q)(n+2)^{O(1)}2^{O(q)}. The method builds a hierarchy of copies of the configuration graph with a shared finite random environment and evaluates a family of O(log⁡n)O(\log n)-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). The paper also claims a deterministic approximation of acceptance probabilities to accuracy 2^-q in space O(log n + q) and an effective compiler from randomized to deterministic logspace machines. There is no Lean formalization for this manuscript in the release. Nothing was re-run here. Note the scope the paper states: it concerns polynomial-time randomized logspace; it does not claim that randomized logspace machines without a time bound are derandomized.

Source

Changelog1 change

Discussion