OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

Theorem 1.1 [Exact logarithmic-space derandomization]: With one-sided or with bounded error, for machines that read one fresh coin per step and halt within polynomially many steps

Randomized logarithmic space equals deterministic logarithmic space.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Throughout, nn is the length of the input. A machine with a logarithmic amount of work space may also flip coins, one at each step. Two ways of letting it err are standard: with one-sided error it never accepts a word outside the language and accepts each word in it with probability at least 1/21/2; with bounded error it answers correctly with probability at least 2/32/3 on every word. In both cases it must halt within polynomially many steps. The question is whether coins let such a machine decide a language that no deterministic machine in logarithmic space decides. The item is Theorem 1.1 of the paper behind the library, an OpenAI preprint of September 2026.

Machines and Runs

A word is a finite binary string✦, and a language is a set of words.✦ The input xx sits between a left and a right end marker on a read-only tape of n+2n+2 cells, numbered 00 to n+1n+1, so that an input symbol is a bit or one of the two markers.

A machine MM with states 0,…,q0, \dots, q, ww binary work tapes, each with one head, and hh heads on the input tape consists of an initial state, an output that gives each state the answer accept, the answer reject or no answer, and a transition function.✦ The transition function reads the state, the hh input symbols under the input heads, the ww bits under the work heads and one coin bit, and returns an action: a next state, a bit to write on each work tape, and for each work head and each input head a move to the left, no move or a move to the right. A halting state of MM is a state to which the output of MM gives an answer, and an accepting state of MM is a halting state whose answer is accept. A machine MM is deterministic when its transition function returns the same action for both values of the coin bit.✦

A configuration of MM on an input of length nn consists of a state, the positions of the input heads in {0,…,n+1}\{0, \dots, n+1\}, the positions of the work heads in ℤ\mathbb{Z}, and the contents of the work tapes, each a binary sequence indexed by ℤ\mathbb{Z}.✦ A coin sequence is an infinite sequence ρ=(ρ0,ρ1,…)\rho = (\rho_0, \rho_1, \dots) of bits.✦ The run of MM on xx under ρ\rho is the sequence of configurations C0,C1,…C_0, C_1, \dots in which C0C_0 is the initial configuration of MM on xx, the configuration with MM in its initial state and the heads and work tapes in their fixed starting positions and contents, and Ct+1C_{t+1} is obtained from CtC_t by one application of the transition function with coin bit ρt\rho_t.✦

The machine MM halts on xx by step tt when, under every coin sequence, the state of CtC_t is a halting state.✦ A machine MM decides a language AA when each word xx has a step tt by which MM halts on xx, and under every coin sequence the answer at step tt is accept if x∈Ax \in A and reject otherwise.

The space sM(x,ρ,t)s_M(x, \rho, t) that MM uses on xx under ρ\rho through step tt is the sum, over the work tapes, of the number of distinct cells that the tape’s head occupies at steps 0,…,t0, \dots, t.✦ A machine MM works in logarithmic space when there is an integer c>0c > 0 with sM(x,ρ,t)≤c⌈log⁡2(n+2)⌉s_M(x, \rho, t) \le c \,\lceil \log_2 (n+2) \rceil(1)✦ for every input xx of length nn, every coin sequence ρ\rho and every step tt.

The acceptance probability of MM on xx at step tt is the fraction of coin strings r∈{0,1}tr \in \{0,1\}^t under which CtC_t is in an accepting state, the coins after rr being zeros: acc⁡M(x,t)=2−t|{r∈{0,1}t:M on x under r0∞ is in an accepting state at step t}|.\operatorname{acc}_M(x, t) = 2^{-t} \, \bigl|\{\, r \in \{0,1\}^t : M \text{ on } x \text{ under } r\,0^\infty \text{ is in an accepting state at step } t \,\}\bigr|.(2)✦

A polynomial clock TT is a function of the input length nn, given by integers c>0c > 0 and k≥0k \ge 0 as in (3), that allots T(n)T(n) steps to an input of length nn: T(n)=c(n+2)k.T(n) = c\,(n+2)^k.(3)✦

The Three Classes

The class 𝖫\mathsf{L} (deterministic logarithmic space) is the set of languages decided by some deterministic machine that works in logarithmic space.✦

The class 𝖱𝖫\mathsf{RL} (randomized logarithmic space with one-sided error) is the set of languages AA for which there are a machine MM working in logarithmic space and a polynomial clock TT such that MM halts on every input xx of length nn by step T(n)T(n) and acc⁡M(x,T(n))≥12 if x∈A,acc⁡M(x,T(n))=0 if x∉A.\operatorname{acc}_M(x, T(n)) \ge \tfrac12 \ \text{ if } x \in A, \qquad \operatorname{acc}_M(x, T(n)) = 0 \ \text{ if } x \notin A.(4)✦

The class 𝖡𝖯𝖫\mathsf{BPL} (bounded-error probabilistic logarithmic space) is the set of languages AA for which there are a machine MM working in logarithmic space and a polynomial clock TT such that MM halts on every input xx of length nn by step T(n)T(n) and acc⁡M(x,T(n))≥23 if x∈A,acc⁡M(x,T(n))≤13 if x∉A.\operatorname{acc}_M(x, T(n)) \ge \tfrac23 \ \text{ if } x \in A, \qquad \operatorname{acc}_M(x, T(n)) \le \tfrac13 \ \text{ if } x \notin A.(5)✦

The Claim

Theorem 1 (Exact logarithmic-space derandomization). The three classes coincide, 𝖫=𝖱𝖫and𝖱𝖫=𝖡𝖯𝖫,\mathsf{L} = \mathsf{RL} \quad \text{and} \quad \mathsf{RL} = \mathsf{BPL},(6)✦ and these four inclusions hold: 𝖡𝖯𝖫⊆𝖫,\mathsf{BPL} \subseteq \mathsf{L},(7)✦ 𝖱𝖫⊆𝖡𝖯𝖫,\mathsf{RL} \subseteq \mathsf{BPL},(8)✦ 𝖫⊆𝖱𝖫,\mathsf{L} \subseteq \mathsf{RL},(9)✦ 𝖫⊆𝖡𝖯𝖫.\mathsf{L} \subseteq \mathsf{BPL}.(10)✦ Let MM be a machine that works in logarithmic space and decides a language AA, and let TT be a polynomial clock such that MM halts on every input of length nn by step T(n)T(n). Then A∈𝖱𝖫∩𝖡𝖯𝖫.A \in \mathsf{RL} \cap \mathsf{BPL}.(11)✦ For every rational number pp with 1/2≤p≤11/2 \le p \le 1, the probability that at least one of two independent trials, each succeeding with probability pp, succeeds satisfies 1−(1−p)2≥34.1 - (1-p)^2 \ge \tfrac34.(12)✦

In the paper, the result reads: 𝖫=𝖱𝖫=𝖡𝖯𝖫\mathsf{L} = \mathsf{RL} = \mathsf{BPL}.

What Is Checked

The claims (6) to (11) are stated over the classes 𝖫\mathsf{L}, 𝖱𝖫\mathsf{RL} and 𝖡𝖯𝖫\mathsf{BPL} above, for machines that read one fresh coin bit at each step, with space bounded as in (1) and acceptance probability as in (2) at a polynomial clock (3), and the claim (12) over the rational numbers.