The Setting
Throughout, 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 ; with bounded error it answers correctly with probability at least 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 sits between a left and a right end marker on a read-only tape of cells, numbered to , so that an input symbol is a bit or one of the two markers.
A machine with states , binary work tapes, each with one head, and 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 input symbols under the input heads, the 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 is a state to which the output of gives an answer, and an accepting state of is a halting state whose answer is accept. A machine is deterministic when its transition function returns the same action for both values of the coin bit.✦
A configuration of on an input of length consists of a state, the positions of the input heads in , the positions of the work heads in , and the contents of the work tapes, each a binary sequence indexed by .✦ A coin sequence is an infinite sequence of bits.✦ The run of on under is the sequence of configurations in which is the initial configuration of on , the configuration with in its initial state and the heads and work tapes in their fixed starting positions and contents, and is obtained from by one application of the transition function with coin bit .✦
The machine halts on by step when, under every coin sequence, the state of is a halting state.✦ A machine decides a language when each word has a step by which halts on , and under every coin sequence the answer at step is accept if and reject otherwise.
The space that uses on under through step is the sum, over the work tapes, of the number of distinct cells that the tape’s head occupies at steps .✦ A machine works in logarithmic space when there is an integer with (1)✦ for every input of length , every coin sequence and every step .
The acceptance probability of on at step is the fraction of coin strings under which is in an accepting state, the coins after being zeros: (2)✦
A polynomial clock is a function of the input length , given by integers and as in (3), that allots steps to an input of length : (3)✦
The Three Classes
The class (deterministic logarithmic space) is the set of languages decided by some deterministic machine that works in logarithmic space.✦
The class (randomized logarithmic space with one-sided error) is the set of languages for which there are a machine working in logarithmic space and a polynomial clock such that halts on every input of length by step and (4)✦
The class (bounded-error probabilistic logarithmic space) is the set of languages for which there are a machine working in logarithmic space and a polynomial clock such that halts on every input of length by step and (5)✦
The Claim
Theorem 1 (Exact logarithmic-space derandomization). The three classes coincide, (6)✦ and these four inclusions hold: (7)✦ (8)✦ (9)✦ (10)✦ Let be a machine that works in logarithmic space and decides a language , and let be a polynomial clock such that halts on every input of length by step . Then (11)✦ For every rational number with , the probability that at least one of two independent trials, each succeeding with probability , succeeds satisfies (12)✦
In the paper, the result reads: .
What Is Checked
The claims (6) to (11) are stated over the classes , and 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.