RL versus L

RL versus L

OpenAI's claim

OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 103; 2026-09-23), the asserted result is that polynomial-time randomized logarithmic space can be simulated deterministically in logarithmic space, giving $\mathrm L=\mathrm{RL}=\mathrm{BPL}$.

Mathematical statement of the claimed result

Manuscript 1.

For uniform polynomial-time, logarithmic-work-space Turing machines, the claimed complexity-class equality is \[ \mathrm L=\mathrm{RL}=\mathrm{BPL}. \] More quantitatively, fix any randomized machine $\mathcal M$ of polynomial worst-case time and $O(\log(n+2))$ work space. Given input $x$ of length $n$ and unary $1^q$, $q\ge1$, a deterministic algorithm is claimed to output an integer $0\le a\le2^{q+2}$ satisfying \[ |a2^{-(q+2)}-p_{\mathcal M}(x)|\le2^{-q} \] in $O(\log(n+2)+q)$ work space and $(n+2)^{O(1)}2^{O(q)}$ time. Constants depend only on the fixed machine.

Outline of the argument

For manuscript 1 (family 103; 2026-09-23), stochastic atoms are assembled with controlled numerical error and bounded suspended storage. Slice-mixing walks are generated without retaining their endpoints, and a fixed bounded-resource interpreter makes the deterministic simulation uniform over source machines.

Formal verification

No Lean formalization is listed at this snapshot for manuscript 1 (family 103; 2026-09-23).

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, Exact Derandomization of Logarithmic Space: L = RL = BPL, 2026-09-23; citation key OAI:Exact-Derandomization-of-Logarithmic-Space-L-equals-RL-equals-BPL-September-23-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main; Statement source: thm:probability.
• OpenAI catalogue entry.

RL versus L

Definitions and mathematical statement

On length-$N$ binary inputs, $\mathrm L$ uses a deterministic machine with read-only input and $O(\log(N+2))$ writable work bits. In the selected $\mathrm{RL}$ model, random bits are unbiased and read once, and the machine halts for every input and every random tape. It must satisfy \[ x\in L\Rightarrow\Pr[\mathrm{accept}]\ge2/3, \qquad x\notin L\Rightarrow\Pr[\mathrm{accept}]=0. \] The question is whether every language with such a randomized logarithmic-space algorithm also has a deterministic logarithmic-space algorithm. Retaining old random bits requires counted workspace. The exact all-random-tapes halting convention is retained, rather than replaced by almost-sure termination or an expected-space bound.

Formulation and concept references: [S1].

Short English statement

Can one-sided-error randomness always be removed from a logarithmic-memory decision algorithm under the stated halting and random-bit conventions?

Research attempt

Scope, process, and first gap.

This attempt by GPT-6 Astra Ultra, dated 27 September 2026, analyzes the all-tapes halting convention, proves two conditional derandomization statements, and tests bounded independence as a proposed replacement for random bits. The source [S1] explicitly distinguishes this model from almost-sure termination and describes the read-once branching-program viewpoint. The deductions below keep both conventions. They are partial arguments, not a new separation or equality theorem.

The first missing step is a logarithmic-space, uniform construction of a small set of random tapes hitting every accepting computation of sufficiently large probability. Existence of a polynomial-size list, or the ability to verify one tape, does not provide that construction.

Halting on every tape gives a polynomial clock.

Fix the randomized machine and an input of length $N$. A configuration records its finite control, input head, work head, and $O(\log(N+2))$ work bits. Its number of possibilities is at most $(N+2)^a$ for a constant $a$ depending on the machine. The absolute position on the fresh random tape need not be stored: previously consumed bits cannot be revisited and the unread suffix is unrestricted.

Make a directed graph of possible transitions, giving a random-bit instruction its two successors. Every configuration reachable before halting lies in an acyclic part of this graph. Indeed a reachable directed cycle could be traversed repeatedly by choosing its finite sequence of random outcomes again and again. This specifies an infinite tape on which the machine never halts, contradicting the stated convention. A cycle containing no random instruction already gives a deterministic infinite run.

Therefore every computation halts within the number of configurations, up to a fixed change in the machine encoding. In particular the machine uses at most \[ T(N)=(N+2)^{O(1)} \] random bits. This conclusion would fail for a procedure that repeatedly flips a coin until its first head: that procedure halts almost surely, but its all-zero tape never terminates.

The proof is about reachable configurations, so irrelevant cycles in an arbitrary syntactic state graph cause no problem. Any currently retained random information must be in finite control or in counted workspace. A hidden reusable random-tape pointer would invalidate the configuration argument.

One-sided error becomes a reachability assertion.

An accepting finite computation has positive probability, since its required random prefix has probability $2^{-r}$ for some finite $r$. Thus on a No input there is no accepting path at all. On a Yes input the acceptance probability is at least $2/3$, so there is an accepting path. The machine can therefore be simulated nondeterministically in logarithmic space, proving the elementary containment \[ \mathrm L\subseteq\mathrm{RL}\subseteq\mathrm{NL}. \] The left inclusion ignores randomness; the right inclusion does not preserve the probability lower bound, which is unnecessary for nondeterministic acceptance.

There is also an explicit deterministic $O(\log^2N)$-space simulation. To test whether a directed configuration graph with $K=\operatorname{poly}(N)$ vertices has a path from $u$ to $v$ of length at most $2^h$, recursively try all middle vertices $z$ and test the two half-length paths. The base case tests equality or one transition. Take $h=\lceil\log_2K\rceil$, and try all accepting target configurations.

At one recursion level, the endpoints, a middle-vertex counter and a level counter need $O(\log K)$ bits. There are $O(\log K)$ levels. Subcalls are made sequentially, so this proves the squared-logarithmic workspace bound without storing the graph. The transition relation is computed from the fixed input as needed. Reducing this recursion stack to one logarithmic factor is not accomplished by observing that the graph itself has polynomially many vertices.

A sufficient small-randomness condition.

Suppose an RL algorithm uses only $c\log(N+2)$ random bits. Enumerate every tape prefix of that length, simulate the algorithm, and accept if any simulation accepts. The prefix and its current position fit in logarithmic space, alongside the machine configuration. The number of prefixes is polynomial, and the halting argument supplies a polynomial simulation clock. This is a deterministic logarithmic-space algorithm.

A generalization makes the desired missing object explicit. Suppose there is a generator \[ G_N:\{0,1\}^{s(N)}\longrightarrow\{0,1\}^{T(N)}, \qquad s(N)=O(\log N), \] whose bit $G_N(z)_j$ can be computed uniformly in $O(\log N)$ workspace from $N,z,j$. Assume that whenever the randomized machine accepts an input with probability at least $2/3$, some seed yields an accepting tape.

Enumerate all seeds and simulate the original machine using the bit procedure at each random instruction. Preserve the current configuration while invoking the generator. A constant number of logarithmic work areas still uses $O(\log N)$ total space. A random-position counter is also logarithmic because $T$ is polynomial. No output tape of length $T$ is retained.

For No inputs every tape rejects, so a hitting guarantee only on Yes inputs suffices. A pseudorandom generator approximating acceptance probabilities within, say, $1/3$ would imply this hitting property, but the two requirements are not identical. One-sided error permits the weaker one.

A small list exists nonuniformly.

For a fixed input length choose $t=N+1$ independent uniform tapes of length $T(N)$. For any particular Yes input the probability that they all reject is at most $3^{-t}$. There are at most $2^N$ inputs, so the probability of missing even one Yes input is at most \[ 2^N3^{-(N+1)}<1. \] Consequently some list of $N+1$ tapes hits all Yes inputs of that length. Its total length is polynomial.

This is an existence proof with the quantifiers \[ \forall N\ \exists\text{ a suitable list at length }N. \] It does not construct a single logarithmic-space algorithm computing those lists. If the list is provided as read-only advice, seed and position counters let the simulation access it with logarithmic work memory. Removing that advice is exactly the missing uniformity step, not a harmless rearrangement of the quantifiers.

Nor can one simply enumerate all candidate lists inside the desired space and choose the first good one. Recognizing that a list hits every relevant accepting computation already entails a global verification problem. Even storing one unrestricted candidate tape requires polynomially many bits if it is represented directly.

Bounded independence misses a tiny branching program.

Fix an integer $r\ge2$ and split $2r$ random bits into two blocks. Consider the event that at least one block has odd parity. Under fully independent bits its probability is $3/4$. A width-four read-once branching program can maintain the two parities and decide this event.

Now choose each block uniformly among its even-parity strings, independently between the blocks. Within an $r$-bit even-parity block, every assignment to at most $r-1$ coordinates occurs equally often: choose the remaining free coordinates and use the final coordinate to satisfy parity. Hence the whole distribution is $(r-1)$-wise independent. Nevertheless the event has probability zero.

Thus arbitrarily large fixed levels of independence do not automatically hit even these width-four programs. The test does not refute any specific carefully designed space-bounded generator; it refutes an argument using only bounded independence. Increasing independence until every bit is independent restores the original randomness cost rather than solving its removal.

Verification and outcome.

Finite checks enumerate the parity-conditioned distributions and their coordinate marginals, and compare the two acceptance probabilities exactly. The workspace accounting explicitly includes generator seeds, random positions, saved configurations and recursive reachability frames. These are distinct resources; a polynomial running-time statement alone does not bound their simultaneous storage.

UNRESOLVED. The all-tapes polynomial clock, a deterministic squared-logarithmic-space simulation, and logarithmic-space simulations under explicit small-randomness or hitting-generator hypotheses are established. The first remaining gap is constructing the required hitting procedure uniformly in logarithmic space for every RL machine, or proving a language separation.

Sources

• S1 William M. Hoza, Recent Progress on Derandomizing Space-Bounded Computation; ECCC TR22-121 Revision1. https://eccc.weizmann.ac.il/report/2022/121/revision/1/download/. Formulation source.