Derandomizing Space-Bounded Computation

Derandomizing Space-Bounded Computation

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.

Derandomizing Space-Bounded Computation

Definitions and mathematical statement

A probabilistic logarithmic-space machine has read-only input, $O(\log n)$ work bits, random bits, and polynomial running time. The class $\mathrm{BPL}$ consists of languages it decides with acceptance probability at least $2/3$ on yes inputs and at most $1/3$ on no inputs. The deterministic class $\mathrm L$ uses the same logarithmic workspace without randomness. Determine whether \[ \mathrm{BPL}=\mathrm L. \] All bounds are uniform over inputs of each length. Space counts writable working storage, not the read-only input or the number of random bits ever read. The question is exact derandomization of the language class, not merely a small increase in the workspace bound.

Formulation and concept references: [S1].

Short English statement

Can randomness always be removed from a polynomial-time decision procedure using logarithmic memory without increasing its memory requirement beyond a constant factor?

Research attempt

Current frontier.

The exact target is a uniform $O(\log n)$ workspace bound. Hoza's general simulation improves the Saks--Zhou bound to $O(\log^{3/2}n/\sqrt{\log\log n})$, not to logarithmic space [E1]. Cheng--Wu's newer weighted generators improve several parameter regimes, including short-wide and regular branching programs; those hypotheses do not cover all polynomial-length, polynomial-width programs arising from BPL [S1], Sections 1.1--1.4. Hitting sets can suffice for two-sided derandomization through a nontrivial reduction, as Cheng--Hoza prove [E2]. None of these results licenses replacing an arbitrary acceptance probability by an easily computed unweighted average over a logarithmic seed.

Attack route.

There are three plausible ways to avoid retaining a long random seed: compute an approximate backward value function, forget old randomness through contraction, or use a signed short-seed quadrature. The first requires a uniform way to generate local approximate values. The second requires quantitative loss of memory in the acceptance observable. The third requires both short descriptions and control of cancellation. I pursue a common error-budget formulation, then try to break each shortcut on elementary examples.

Attempt: an occupancy-weighted residual identity.

Fix an input of length $n$ and pad the probabilistic machine to exactly $T\le n^c$ steps. Its configurations fit in $O(\log n)$ bits. By adding a layer index, it becomes a read-once branching program with stochastic transition matrices $P_0,\ldots,P_{T-1}$ on at most $n^c$ states; each row can be computed in logarithmic space. The terminal function $f$ is the indicator of acceptance. Let $X_i$ be the random state at layer $i$.

For arbitrary real functions $v_i$ on the layers define \[ r_i(v)=v_i(v)-(P_iv_{i+1})(v),\qquad 0\le i<T. \] The following exact identity is useful: \begin{equation}\label{wsref-0-33-30-30-30-34-39-32-32-3a-72-65-73-69-64-75-61-6c} v_0(x_0)-{\mathbb{E}} f(X_T) =\sum_{i=0}^{T-1}{\mathbb{E}} r_i(X_i) +{\mathbb{E}}\left(v_T(X_T)-f(X_T)\right). \end{equation} It follows by summing ${\mathbb{E}} v_i(X_i)-{\mathbb{E}} v_{i+1}(X_{i+1})={\mathbb{E}} r_i(X_i)$. Everything is finite. In particular, \begin{equation}\label{wsref-0-33-30-30-30-34-39-32-32-3a-72-65-73-69-64-75-61-6c-2d-62-6f-75-6e-64} |v_0(x_0)-\Pr(\mathrm{accept})| \le\sum_{i<T}\|r_i\|_\infty+\|v_T-f\|_\infty. \end{equation} This distinguishes an exact occupancy-weighted error budget from a potentially much worse uniform local budget.

Sufficient value-generator lemma. Suppose that, uniformly for every such program, a deterministic logarithmic-space algorithm outputs $v_i(v)$ as a dyadic rational with $O(\log n)$ bits, and that \[ \|v_T-f\|_\infty\le1/24, \qquad\sum_{i<T}\|r_i\|_\infty\le1/24. \] Then BPL is contained in L: compute only $v_0(x_0)$ and compare it with $1/2$. The error at most $1/12$ separates acceptance probabilities at least $2/3$ from those at most $1/3$. The reverse inclusion is immediate. No table of all configurations is stored in this algorithm.

The hypothesis is not obtained simply by rounding the true backward probabilities. Such rounding does show that suitable polynomial-size tables exist: with denominator $2^b$, $b=O(\log T)$, one can make each residual $O(1/T)$. It does not supply a logspace generator for their entries. A polynomial-size table of dyadic values can be checked in logspace when provided on a separate read-only certificate tape, by looping over its rows. That is a different resource from computing the table deterministically. Treating the certificate as free advice would violate the target's uniformity.

Attempt: a genuine contraction subclass.

Let $\ell\le C\log n$ be an explicitly specified number of final random steps. Suppose that the laws of the terminal state, started at any two states $u,v$ of layer $T-\ell$, differ in total variation by at most $1/12$. Then the acceptance probability is deterministically approximable within $1/12$ in logarithmic space: select any fixed state of that layer, enumerate the $2^\ell$ suffixes of random bits, simulate them, and count accepting suffixes. A suffix, a configuration, the loop index, and the counter each occupy $O(\log n)$ bits. Time is polynomial. The true distribution at layer $T-\ell$ is a mixture of the possible starting states, and the total-variation hypothesis bounds its difference from this fixed-state computation.

This criterion is slightly stronger than needed: it suffices that the acceptance probabilities from those states differ by at most $1/12$, rather than their full terminal laws. However, certifying that weaker condition by first computing all acceptance probabilities is circular. The criterion is a solved subclass, not an argument that every branching program has a rapidly contracting suffix.

Attempt: signed quadrature and bit complexity.

Here is another precise sufficient input. Suppose a uniform logarithmic- space procedure generates, for $r\in\{0,1\}^d$, a $T$-bit string $G(r)$ one bit at a time and a weight $w_r=z_r2^{-b}$, where \[ d,b\le C\log n,\qquad |z_r|\le n^C, \qquad \left|\Pr(\mathrm{accept})-\sum_r w_r f(G(r))\right|<1/12. \] Enumerating all seeds and accumulating the integers $z_rf(G(r))$ uses only $O(\log n)$ space: the absolute numerator is at most $2^d n^C$, and the common denominator has $O(\log n)$ bits. The generated bits can be recomputed whenever needed. This would again yield BPL=L. The inclusion of the weight encoding is essential; a short seed alone does not bound the space needed for exponentially precise signed weights. Weighted generators are an established framework [S1]; the specific unrestricted logarithmic parameters above are the missing input, not an application of a cited theorem.

Can local signed compressions be composed without increasing that cost? For matrices with the operator norm induced by $\ell^\infty$, telescoping products gives \begin{equation}\label{wsref-0-33-30-30-30-34-39-32-32-3a-70-72-6f-64-75-63-74-2d-65-72-72-6f-72} \|P_0\cdots P_{T-1}-Q_0\cdots Q_{T-1}\|_\infty \le\sum_{i=0}^{T-1} \|P_i-Q_i\|_\infty \prod_{j<i}\|Q_j\|_\infty. \end{equation} Indeed, insert $Q_0, Q_1,\ldots$ successively on the left and keep the remaining $P$ matrices on the right; stochastic matrices have norm one. Thus a controlled sum of local errors is insufficient when signed intermediate matrices have large absolute row sums.

Stress test: three explicit failures.

First, an absorbing accepting state and an absorbing rejecting state never mix: their terminal laws remain at total-variation distance one. This can happen in a deterministic logspace computation. Therefore rapid mixing is not even a necessary structural property of problems in L, and cannot be asserted for all BPL computations without a further transformation that preserves the answer.

Second, preservation of constants is not the same as norm stability. For $a>0$, \[ Q=\begin{pmatrix}1+a&-a\\-a&1+a\end{pmatrix} \quad\text{satisfies}\quad Q\binom11=\binom11, \qquad Q^t\binom1{-1}=(1+2a)^t\binom1{-1}. \] Every row sums to one, yet errors in the antisymmetric direction are exponentially amplified. At $a=1/4$, twelve applications amplify that direction by $(3/2)^{12}$, verified exactly in the script. This is a counterexample to the proposed stability lemma, not to BPL=L.

Third, even a recursion of only $O(\log n)$ levels can multiply polynomial absolute-weight budgets into $n^{O(\log n)}$. Directly accumulating such numerators may require $\Theta(\log^2 n)$ bits. Avoiding this cost would need a compensated composition, a norm in which the intermediate operators remain controlled, or a different use of hitting sets such as the framework of [E2]. I have not derived such a uniform composition rule with logarithmic workspace.

The value-generator lemma is also adversarially checked for rounding: per-layer errors of a fixed constant would sum to order $T$, and so cannot be used. The required $O(1/T)$ scale is cheap to encode, but not thereby cheap to compute. That is the exact point where the attempted conversion of local verification into a deterministic simulation stops.

Outcome.

Outcome: Exploratory approach with unresolved gap.

The residual identity, the contraction-subclass simulation, the signed- quadrature bit bound, and the product-error estimate are proved. They provide compatible tests for a proposed derandomization mechanism and exhibit concrete failures of memory erasure and signed-weight stability. No general logspace value generator or stable logarithmic-seed quadrature has been constructed. The additional input needed for either would already imply the full language-class equality, not merely a small improvement in workspace.

\Needspace{12\baselineskip}

Sources

• S1 Kuan Cheng and Ruiyang Wu, Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions, Introduction. https://arxiv.org/html/2502.08272v5. Catalogue formulation source.
• E1 William M. Hoza, "Better Pseudodistributions and Derandomization for Space-Bounded Computation," APPROX/RANDOM 2021, LIPIcs 207, article 28, 28:1--28:23. Main generator and deterministic-space consequences. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.28. Author summary and proceedings version distinguish the improved bound from logarithmic space.
• E2 Kuan Cheng and William M. Hoza, "Hitting Sets Give Two-Sided Derandomization of Small Space," Theory of Computing 18 $2022$, article 1, 1--32. Main derandomization theorem. https://williamhoza.com/research/papers/CH/. A two-sided hitting-set framework, not an unrestricted logarithmic-seed construction.