AI Proved What?

Episode 103, October 2026

Coins don’t help?

A claimed proof that L = RL = BPL: randomness adds nothing to logarithmic-space computation

Covers result 103 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.

Play Episode 103: Coins don’t help? A time-layered configuration graph with one random path from the start to acceptance, and a crossed-out coin.

6:13. English captions available. The video loads from YouTube when you press play.

Chapters

  1. 0:00Randomness in small space
  2. 2:14The claims
  3. 3:36How the proof goes
  4. 5:32Where it stands

The claims, in plain words

A logarithmic-space machine reads its input freely but can write only about log n bits: room for a few counters and pointers into the input, not for a copy of it. L is the class of problems such machines decide deterministically; they automatically run in polynomial time. RL and BPL give the machine fresh random coins and require polynomial time: RL never accepts a no-instance and accepts a yes-instance with probability at least 1/2, and BPL errs with probability at most 1/3 either way. The classic example is undirected connectivity: Aleliunas, Karp, Lipton, Lovász and Rackoff showed that a polynomial-length random walk finds a connected target, and asked whether such computations can be done deterministically in logarithmic space.

Nisan’s pseudorandom generator replaced the coins with a seed of O(log² n) bits, and Nisan later simulated these machines deterministically in polynomial time and O(log² n) space. Saks and Zhou reduced the space to O(log3/2 n), without the polynomial time bound, and Hoza improved this by a factor of about √(log log n). Reingold’s 2005 algorithm put undirected connectivity in L, but general directed computations stayed open. Cheng and Hoza showed that a suitable hitting-set construction for read-once branching programs would give L = BPL.

Result 103 is one OpenAI preprint (108 pages) dated September 23, 2026. It claims L = RL = BPL. More precisely, for any randomized machine with polynomial running time and logarithmic space, a deterministic algorithm approximates its acceptance probability within 2−q, using O(log n + q) space and (n + 2)O(1)·2O(q) time; any fixed inverse-polynomial accuracy therefore costs only logarithmic space and polynomial time. The paper also gives an effective compiler that turns a bounded-error randomized program, with supplied time and space bounds, into a deterministic decider with explicit bounds.

What it doesn’t claim

The question for polynomial time, whether BPP = P, is separate and untouched. The randomized classes here require polynomial running time; randomized logarithmic-space machines without a time bound, studied by Borodin, Cook and Pippenger, are a different setting. The paper does not go through a hitting-set construction; it takes a different route, through a matrix inverse.

Where it stands

Posted as a preprint
OpenAI, 108 pages, dated September 23, 2026, released October 6
Peer reviewed
Not yet
Checked in Lean
OpenAI published a Lean proof of the class equality; we have not run the check

Last checked October 19, 2026. The preprint has not been revised. OpenAI published a Lean formalization, 39 files and 43,045 lines in an explicit Turing-machine model, matched against its comparator statement L = RL ∧ RL = BPL, with no unproved steps that we could find. The compiler and the explicit bounds are not part of that target. By our reading, the formalization follows a variant of the paper’s route: it proves its own mixing bound by an elementary Fourier argument instead of citing Shalom’s property (T) results, compares endpoints exactly instead of by fingerprints, uses fourth moments and ends with an exact average. We have not run the check. The paper is not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

  1. A matrix inverse. Stamp every configuration of the machine with the time, so every transition moves forward. The transition probabilities form a strictly forward substochastic matrix S, and the acceptance probabilities from every configuration are p = (I − S)−1e, where e marks the accepting configurations.
  2. Corrections and copies. A correction replaces a transition matrix C by D = C − E + EC. Then I − D = (I + E)(I − C), so the removed transitions move into a reward: (I − C)−1r = (I − D)−1(I + E)r. Copy steps split vertices to spread large entries. After l stages the error is at most |V0|·2−(H−1)l for a fixed H ≥ 4, so O(log n) stages give inverse-polynomial accuracy, with polynomially many vertices at each stage.
  3. One random environment. Each estimate uses one random environment of O(log n) bits, shared by all its recursive parts. Sampled tables with few entries per row stand in for the exact matrices; conditional averaging, with a mixing bound from Shalom’s results on property (T), reduces the noise; lists are compressed into exceptions to a default; and endpoints are compared by short fingerprints from polynomial evaluation and affine hashing. An eighth-moment bound shows that more than three quarters of the relevant environments give an accurate estimate.
  4. Logarithmic space. Each recursive call gets an allowance, and the data it keeps is bounded by multiples of the change in allowance and the change in the requested digit place, so the bounds telescope along any chain of calls. Digits are requested one at a time, a shared catalytic bit vector serves the fingerprint comparisons and is restored, and incoming edges are found by traversing program trees, with the contour idea of Cook and McKenzie. Every estimate halts in logarithmic space, accurate or not; enumerating the relevant environments, taking the median and comparing it with 1/2 decides the language deterministically.

The numbers in the video

  • A toy randomized machine, a weighted random walk on 6 vertices for 8 steps (54 time-stamped configurations): (I − S)−1e gives acceptance probability 0.0838 from the start; a simulation of 200,000 runs gives 0.0839.
  • The correction identity I − D = (I + E)(I − C), with the reward transfer, on 200 random examples: largest error about 9 × 10−16.
  • Space at n = 109 with constants set to 1: log n ≈ 30 bits, Hoza’s bound ≈ 74, log3/2 n ≈ 163, log² n ≈ 894.
  • Random walks of length 2|V||E| on random connected 60-vertex graphs: 400 of 400 found the target.
  • If more than three quarters of a list of estimates are within 1/8 of the truth, so is the median: 2,000 of 2,000 random trials with the bad estimates placed far away.

Read the source

The paper

OpenAI groups related papers into one result; this one has a single paper.

Transcript

Read the full script

0:00Randomness in small space

A logarithmic-space machine reads its input freely but can write only about log n bits: room for a few counters and pointers into the input, not for a copy of it. L is the class of problems such machines decide deterministically, and they automatically run in polynomial time. Now give the machine fresh random coins, require polynomial time, and allow error. RL allows one-sided error: it never accepts a wrong instance, and accepts a right one at least half the time. BPL allows two-sided error, at most 1/3 either way. The classic example is a random walk. To test whether two vertices of an undirected graph are connected, walk at random. Aleliunas, Karp, Lipton, Lovász and Rackoff showed that a polynomial-length walk suffices, and asked whether the coins can be removed. In our test on random 60-vertex graphs, all connected, every walk found its target. Nisan’s pseudorandom generator replaced the coins with a seed of order log² n bits, and Nisan later simulated these machines deterministically in polynomial time and log² n space. Saks and Zhou brought the space down to log^(3/2) n, without the polynomial time bound, and Hoza improved that slightly. For undirected connectivity, Reingold’s algorithm of 2005 removed the randomness entirely, but general directed computations stayed open. Constants aside, for an input of a billion (10⁹) symbols, log n is about 30 bits, log^(3/2) n about 160, and log² n about 900. The starting point is linear algebra. Stamp every configuration of the machine with the time, so that every transition moves forward. The transition probabilities then form a matrix S, and the vector of acceptance probabilities from every configuration is the inverse of I − S, applied to the indicator of accepting configurations. In our toy machine, a random walk on 6 vertices for 8 steps, this inverse gives about 0.084 for the start, matching a simulation of 200,000 runs.

2:14The claims

Result 103 is one OpenAI preprint, 108 pages, dated September 23. It claims L equals RL equals BPL. More precisely, for any randomized machine with polynomial running time and logarithmic space, a deterministic algorithm approximates its acceptance probability within 2^(−q), using space O(log n + q), and time polynomial in n times 2^(O(q)). So any fixed inverse-polynomial accuracy costs only logarithmic space and polynomial time. The paper also gives an effective compiler that turns a bounded-error randomized program, with supplied time and space bounds, into a deterministic decider with explicit bounds. The question for polynomial time, whether BPP equals P, is separate and untouched. Cheng and Hoza had shown that a suitable hitting-set construction for branching programs would also give this result; the paper takes a different route, through the matrix inverse. OpenAI published a Lean formalization, 39 files and about 43,000 lines, in an explicit Turing-machine model. Its target is the equality of the three classes; the compiler and the explicit bounds are not part of it. We have not run the check.

3:36How the proof goes

The proof estimates that matrix inverse, stage by stage. A correction step replaces a transition matrix C by D, equal to C − E + EC. Then I − D factors as (I + E)(I − C), so the removed transitions move into a reward. In our check on 200 random examples, this identity held to rounding error. Copy steps split vertices to spread large entries. Each stage shrinks the error bound by a fixed factor, so a logarithmic number of stages gives inverse-polynomial accuracy, with only polynomially many vertices at each stage. Each estimate uses one random environment, described by order log n bits, shared by all its recursive parts. Sampled tables with few entries per row stand in for the exact matrices. Conditional averaging, with a mixing bound from Shalom’s results on property T, reduces the noise. Lists are compressed into exceptions to a default, and endpoints are compared by short fingerprints, from polynomial evaluation and affine hashing. A moment bound shows that more than 3/4 of the relevant environments give an accurate estimate. The space accounting is the delicate part. Each recursive call gets an allowance, and the data a call keeps is bounded by multiples of the change in allowance and the change in the requested digit place, so the bounds telescope along any chain of calls. Digits are requested one at a time, a shared catalytic bit vector serves the fingerprint comparisons, and incoming edges are found by traversing program trees, the contour idea of Cook and McKenzie. Every estimate, accurate or not, halts in logarithmic space. Enumerating the polynomially many relevant environments, taking the median, and comparing it with 1/2 decides the language deterministically.

5:32Where it stands

The preprint is not peer reviewed and has not been revised. The Lean formalization covers the class equality, by a variant of the paper’s route: it proves its own mixing bound instead of citing Shalom’s results, and compares endpoints exactly instead of by fingerprints. We have not run it. It is not among the papers OSVerify reviewed, and we have seen no expert review. If it holds, coins add nothing to deciding problems in logarithmic space and polynomial time: every such bounded-error randomized algorithm has a deterministic logarithmic-space counterpart.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.