Derandomization of logarithmic space — L = RL = BPL

← All digests

Family 103 · Theoretical computer science
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-08

A computer can inspect a large input while retaining very little working memory. Randomness often helps such a machine explore possibilities without storing its history. Family 103 claims that, for polynomial-time decisions with bounded error, random bits add no power when working memory is logarithmic in the input length. The proposed simulation removes randomness while preserving that stringent memory bound.

1. The question

Imagine navigating a large network while remembering only your current location and a few counters. You cannot store the set of places already visited. A random walk offers a natural strategy: repeatedly choose a neighboring vertex and hope eventually to reach the destination.

More generally, a small-memory program may read fresh random bits to choose its next action. If it usually gives the correct answer, can a deterministic program always give that answer using the same order of memory and still finish in polynomial time?

The claimed equality

$$\mathsf L=\mathsf{RL}=\mathsf{BPL}$$

answers yes for the standard bounded-error logarithmic-space model. The letters name classes of decision problems, which will be defined below. This is a statement about computation under a simultaneous time and memory constraint.

2. Background and essential definitions

Why logarithmic memory is so restrictive

For an input of length $n$, an integer identifying one input position requires about $\log_2 n$ bits. Thus $O(\log n)$ memory holds a fixed number of positions, counters, or similarly sized quantities. It cannot hold a list of $n$ visited vertices.

The input is on a read-only tape and is not charged to working memory. The machine may revisit it. Everything writable that remains in use does count, including temporary numerical values and the information needed to resume a suspended subroutine. An output tape, when used, is write-only.

A configuration records the machine’s state, head positions, and work-tape contents. A fixed machine using $O(\log n)$ bits has only polynomially many possible configurations. If a deterministic machine halts, it cannot revisit the same complete configuration: doing so would repeat the same future forever. Consequently, a halting deterministic log-space machine also has a polynomial running-time bound.

Three classes of decisions

A language is a set of finite input strings; deciding it means answering whether a given string belongs to the set. The classes in the title have these meanings:

Class	Randomness and error	Working memory
$\mathsf L$	Deterministic, always correct	$O(\log n)$
$\mathsf{RL}$	Never accepts a no-instance; accepts a yes-instance with probability at least $1/2$	$O(\log n)$
$\mathsf{BPL}$	Accepts a no-instance with probability at most $1/3$, a yes-instance with probability at least $2/3$	$O(\log n)$

The randomized machines must run in polynomial time on every sequence of random bits. Their coins are fresh independent fair bits. The error bounds are per input, not averages over a distribution of inputs.

The particular constants are conventional. For example, a one-sided algorithm can be repeated a constant number of times, accepting if any run accepts, to reduce its failure probability. The repetitions reuse memory. It follows that

$$\mathsf L\subseteq\mathsf{RL}\subseteq\mathsf{BPL}.$$

The difficult direction is the reverse containment: removing randomness from an arbitrary two-sided bounded-error computation.

Why trying every random tape is not enough

A computation using $R$ random bits has $2^R$ possible random tapes. If $R$ is polynomial in $n$, listing all tapes takes exponential time, and even storing the current tape index can exceed logarithmic memory.

A pseudorandom generator replaces those tapes by outputs derived from short seeds. The outputs need only look random to the restricted class of computations being simulated. A seed of length $c\log n$, for fixed $c$, has only $n^c$ possibilities. A seed of length $(\log n)^2$ has $n^{\log n}$ possibilities, already beyond polynomial time. The difference between one logarithm and two therefore has major consequences.

3. Development history and previous partial results

In 1979, Aleliunas, Karp, Lipton, Lovász, and Rackoff showed how random walks solve undirected connectivity with little memory. This gave a concrete example of the broader question: was randomness essential, or merely a convenient way to explore a graph?

Nisan’s 1992 generator supplied short pseudorandom sequences for space-bounded computations. For space $S$ and $R$ random bits, its seed length is $O(S\log R)$. With logarithmic space and polynomially many random bits, this becomes $O((\log n)^2)$. Enumerating all seeds gives a useful deterministic simulation, but not the desired polynomial-time, logarithmic-space combination. Nisan’s later simultaneous simulation obtained polynomial time with squared-logarithmic space.

Saks and Zhou reduced the deterministic space needed for general bounded-error log-space computation to $O((\log n)^{3/2})$. Hoza’s 2021 work improved that space bound to

$$O\!\left(\frac{(\log n)^{3/2}}{\sqrt{\log\log n}}\right).$$

These are advances toward the memory target. A smaller-space simulation and a simulation with a simultaneous polynomial-time guarantee are different accomplishments; one should not silently attach the latter guarantee to every space-containment theorem.

Reingold’s undirected connectivity algorithm, presented in 2005 and published in journal form in 2008, reached deterministic logarithmic space for the original random-walk example. But undirected graphs possess symmetry absent from general computation graphs. Solving that special case did not settle arbitrary randomized log-space computation.

Family 103 claims to reach the full target: deterministic logarithmic space and polynomial time for all machines in the bounded-error model. It also describes a compiler that constructs the deterministic simulator from a randomized program with supplied resource bounds.

4. What the new manuscripts claim

The family consists of one manuscript. Theorem 1.1 states the class equality in the title. Its quantitative foundation is Theorem 1.2, concerning acceptance probabilities even when no yes/no probability gap is promised.

Fix a polynomial-time randomized log-space machine $M$. Let $p_M(x)$ be the probability that it accepts input $x$, whose length is $n$. Given an accuracy parameter $q\ge1$, the claimed deterministic algorithm outputs a dyadic rational $\widehat p$, meaning a rational with a power-of-two denominator, such that

$$|\widehat p-p_M(x)|\le2^{-q}.$$

The stated resources are

$$\begin{aligned} \text{work space}&=O(\log(n+2)+q),\\ \text{time}&=(n+2)^{O(1)}2^{O(q)}. \end{aligned}$$

The parameter is supplied in unary as $1^q$, a string of $q$ ones. The constants may depend on the fixed source machine.

For $q=3$, the error is at most $1/8$, smaller than the distance $1/6$ between either bounded-error threshold and $1/2$. Comparing the estimate with $1/2$ therefore gives an exact decision. Taking $q$ proportional to $\log n$ yields inverse-polynomial accuracy while retaining logarithmic space and polynomial time.

Theorem 13.1 adds effectivity: given a source machine and supplied polynomial-time and logarithmic-space bounds, one terminating compiler produces a deterministic decider together with explicit resource bounds. The compiler assumes the source satisfies the supplied bounds; it does not decide that property for arbitrary programs.

5. Why the advance matters

Randomness and memory can substitute for each other. A random walk avoids recording an elaborate route; a deterministic search often remembers more of its progress. The claimed result would show that this apparent advantage of randomness disappears at the level of log-space decision classes, even while retaining polynomial time.

The probability-estimation statement also goes beyond saying that some deterministic decider exists. It offers a common numerical task from which many decisions follow. When a computation’s acceptance probability is separated from a threshold by an inverse-polynomial margin, a sufficiently accurate estimate can decide which side it lies on.

Importance: 5/5, provisional. An equality of these central complexity classes would resolve a longstanding general derandomization problem, encompassing many algorithms rather than a single application. The score reflects that breadth, not a claim that the resulting simulation is immediately practical.

6. The main idea

Turn the computation into linear algebra

Attach a time coordinate to each configuration. Every transition then moves forward, so the configuration graph has no directed cycle. Let $S$ be its transition matrix, with accepting terminal states represented by a vector $e$. Rows of $S$ have nonnegative entries summing to at most one; missing probability corresponds to stopping.

Because a polynomial time bound limits the number of layers, some power $S^{T+1}$ is zero. The acceptance-probability vector can be expressed as

$$p=(I-S)^{-1}e=(I+S+S^2+\cdots+S^T)e,$$

where $I$ is the identity matrix. Each power accounts for paths of a particular length. This makes the target precise, but storing even one full vector would exceed the memory budget.

Estimate individual quantities and recompute the rest

The proposed algorithm therefore treats matrices and vectors as quantities whose entries can be generated when needed. A hierarchy of corrections and configuration copies moves probability contributions into accumulated rewards, while controlling the transitions that remain. It estimates entries through sparse descriptions rather than maintaining complete arrays.

The difficult resource is everything that stays live during recursion. If each of $\log n$ nested calls saved a configuration address of $\log n$ bits, the stack alone would use squared-logarithmic space. The manuscript uses short fingerprints to compare addresses, recomputes information that would otherwise be saved, and requests numerical values one digit at a time.

Its memory accounting assigns a decreasing allowance to recursive calls. A parent’s retained data are charged to the allowance lost when descending to its child. Such differences can telescope along the active call chain, bounding the total rather than bounding each call separately. This is the claimed mechanism for avoiding a hidden extra logarithm.

Enumerate a small family of estimates

The construction uses a finite family of environments described with $O(\log n)$ bits. More than three quarters of the relevant estimates are claimed to be accurate, and every estimate can be evaluated by a halting deterministic log-space procedure, including inaccurate ones.

There are only polynomially many descriptions. The final algorithm enumerates them and finds a median by repeated scans, retaining counters and current candidates instead of sorting a stored list. If most estimates lie within a prescribed interval around the truth, so does their median.

This explains how randomness can enter the analysis without appearing in the final machine. A probabilistic argument establishes that enough members of a small family work; exhaustive deterministic processing of that family extracts the answer. The paper’s main technical burden is constructing the family and evaluating each member within the memory budget.

7. Scope, limitations, and open questions

“Exact” refers to the resulting decisions and the logarithmic order of the space bound. It does not mean every acceptance probability is output as its exact rational expansion. Greater numerical precision costs additional memory and time according to the displayed bounds.

The result concerns polynomial-time computations with fresh random bits and logarithmic working space. It does not assert $\mathsf P=\mathsf{BPP}$, the analogous general polynomial-time derandomization statement without this memory restriction. Nor does it give a deterministic solution to every problem in $\mathsf{NP}$.

The input may be reread. Consequently, the theorem is not automatically a one-pass streaming algorithm for data that cannot be revisited. Similarly, an arbitrary reusable random tape is a different computational model from a stream of fresh independent bits.

Polynomial time permits large exponents and constants depending on the source machine. The compiler’s explicit bounds establish a theoretical resource guarantee; obtaining a practical implementation with competitive running time is a separate question. The claimed result addresses whether randomness increases decision power under these constraints, not whether removing it is always a good engineering choice.

8. Sources and further reading

Exact Derandomization of Logarithmic Space: L = RL = BPL, credited to OpenAI, September 23, 2026. Theorems 1.1–1.2 state the main claims; Section 1.2 explains the construction; Theorem 13.1 gives the compiler statement.

The historical papers are linked in Section 3. Optional background: space complexity, randomized algorithms, and pseudorandom generators in complexity theory.

Source revision: adc7f1241b42. Sources consulted: October 8, 2026. Citation data: BibTeX.

See the series’ AI declaration for authorship and review status. Back to the family index.