betaFeedback

WorksComputer Science

Simulating Space Bounded Read-kk PTMs with Space Bounded Read-Once PTMs

Abstract

We show that read-kk Probabilistic Turing Machines with bounded space SS and running time TT can be simulated by read-once Probabilistic Turing Machines with error ε\varepsilon, running in space O(k2(S+log⁡(n+T))+log⁡(1/ε)) O(k^2 (S + \log (n+ T)) + \log (1/ε)) and time 1ε⋅2O(k2(S+log⁡(n+T)))\frac{1}{\varepsilon} \cdot 2^{O\left(k^2\left(S+\log(n+T) \right)\right)}. As a direct consequence we show that read-kk BPL\mathsf{BPL} is equal to BPL\mathsf{BPL}, for any constant kk. Recently OpenAI announced that BPL=L\mathsf{BPL} = \mathsf{L}. If this is true then our result immediately implies that read-kk BPL\mathsf{BPL} is equal to L\mathsf{L}.

Introduction

Probabilistic Turing Machines (PTMs) with bounded space and bounded time are classic objects studied in computational complexity. The way of accessing randomness in such models may affect the computation power significantly. We mainly review the literature for bounded-error PTMs under two different settings of randomness accessing, with a special focus on the case of logspace machines.

The study of space-bounded randomness has developed along two related directions: computation with fresh random bits, equivalently read-once access to a random tape, and computation with two-way access to a persistent random tape. At logarithmic space and polynomial time, these models define BPL and BP · L, respectively. Gill’s foundational work [10] studied probabilistic Turing machines whose transitions use coin tosses, corresponding to the fresh-coin model. Aleliunas, Karp, Lipton, Lovász, and Rackoff [1] subsequently gave a randomized logarithmic-space algorithm for undirected connectivity using fresh random choices. For arbitrary space-bounded machines in this read-once randomness model, Borodin, Cook, and Pippenger [2] obtained deterministic simulations using quadratic space. The importance of the access convention was already apparent in work of Karpinski and Verbeek [16, 17], who studied two-way random tapes under space bounds without a polynomial-time restriction and established limitations on deterministic space simulation. Their resource convention differs from the polynomial-time two-way model defining BP · L. In the early 1990s, Nisan [21] constructed a pseudorandom generator with O(log⁡2n)O(\log^2 n) seed length that fools polynomial-time, logarithmic-space computations with read-once access to randomness at inverse-polynomial error. Enumerating its seeds yields an O(log⁡2n)O(\log^2 n)-space deterministic simulation; Nisan’s subsequent work [20] achieved polynomial time and O(log⁡2n)O(\log^2 n) space simultaneously for the same read-once source model. In a separate comparison of randomness-access models [22], he showed that every language in BPL admits a zero-error logarithmic-space algorithm with two-way access to randomness, and characterized BP · L as almost-L, the languages decidable in logarithmic space relative to almost every oracle. For read-once source computations using relatively few random bits, Nisan and Zuckerman [23] showed how to reduce poly⁡(S)\operatorname{poly}(S) fresh random bits to O(S)O(S) random bits while retaining O(S)O(S) space and approximately preserving the output distribution. Moving beyond read-once access, Impagliazzo, Nisan, and Wigderson [15] constructed pseudorandom generators for machines whose two-way random-tape head visits each cell only constantly many times. Their result gives O(log⁡2n)O(\log^2 n) seed length for this bounded-local-rereading model at logarithmic space, polynomial time, and inverse-polynomial error. For read-once randomized computation, Saks and Zhou [SZ99] improved the deterministic space bound to O(log⁡3/2n)O(\log^{3/2} n), without a polynomial-time guarantee. Saks [Sak96] surveyed the different conventions for space-bounded randomness. For the unrestricted two-way randomness model, Klivans and van Melkebeek [18] obtained conditional derandomization through space-efficient hardness-versus-randomness constructions: an exponential circuit lower bound, at all sufficiently large input lengths, for a function computable in deterministic linear space implies BP⋅L=LBP \cdot L = L. Gutfreund and Viola [11] gave constructions yielding randomness-efficient error reduction for BP⋅LBP \cdot L, where the random description may be reread. For the specific problem of undirected connectivity, Reingold [Rei05] obtained a deterministic logarithmic-space algorithm. Applications of two-way randomness appeared in many algorithmic applications. For example the work of Flaxman and Frieze [8] considers a space-bounded computation which must reconstruct the same randomly perturbed graph on subsequent accesses. Healy [13] developed computationally efficient samplers and randomness-efficient error reduction in small uniform circuit classes, explicitly distinguishing rereadable randomness from the read-once setting. More recently, Hoza [14] improved the deterministic space bound for read-once randomized computation to O(log⁡3/2n/log⁡log⁡n)O(\log^{3/2} n/\sqrt{\log\log n}), again without a polynomial-time guarantee. Bisht, Gupta, Nimbhorkar, and Volkovich [3] placed arithmetic-formula polynomial identity testing in BP⋅LBP \cdot L, illustrating the role of persistent randomness in reusing a random evaluation point. For read-once randomness, the recent preprint of OpenAI [24] states a deterministic logarithmic-space simulation together with additive inverse-polynomial acceptance-probability approximation. For two-way randomness with a constant local visit bound, Cheng and Wu [4] obtained a deterministic simulation using polynomial time and O(log⁡2n)O(\log^2 n) space, with an inverse-polynomial additive error for the acceptance probability. There is a natural question behind the development of studying the two random access models: as the permitted number of visits to each random-tape cell increases, when can the resulting computation still be simulated using read-once randomness without increasing its asymptotic space bound?

Towards addressing this question, we study the read-multiplicity model of Impagliazzo, Nisan, and Wigderson [15]. We use the following formal definition to describe such models. If we bound the number of visits for the cells in the random tape we come to the class of read-kk PTMs.

Definition 1.1 (Locally Read-kk Machine). Let k:N→N≥1k : \mathbb{N} \to\mathbb{N}_{\ge1}. A locally read-kk machine is a probabilistic Turing machine with a two-way read-only input tape, a read–write work tape, and a read-only random tape satisfying the following conditions.

  • Local access to randomness. The random-tape cells are indexed by 1,2,…1,2,\ldots and contain independent uniformly random bits. The random head starts at cell 1. At each step, it either stays at its current cell or moves to an adjacent cell, without moving left of cell 1. Once the random-tape contents are fixed, the computation is deterministic.

  • Bounded visits. A visit to a random-tape cell is a maximal consecutive period during which the random head remains at that cell. The initial placement at cell 1 begins its first visit. For every input of length nn and every assignment to the random tape, each random-tape cell is visited at most k(n)k(n) times.

Definition 1.2 (LocalReadk_k-BPTISP(TT, SS)). Let kk, TT, S:N→N≥1S : \mathbb{N} \to\mathbb{N}_{\ge1}. The class LocalReadk_k-BPTISP(TT, SS) consists of all languages LL for which there exists a locally read-kk machine MM that halts within O(T(n))O(T(n)) time and uses O(S(n))O(S(n)) work space on every input of length nn and every random tape. Moreover, for every input xx,

x∈L⇒Pr⁡r[M(x;r) accepts]≥23,x \in L \Rightarrow\Pr_{r}[M(x;r)\text{ accepts}] \ge\frac{2}{3},
x∉L⇒Pr⁡r[M(x;r) accepts]≤13.x \notin L \Rightarrow\Pr_{r}[M(x;r)\text{ accepts}] \le\frac{1}{3}.

We write

LocalRead⁡k-BPSPACE(S(n)):=LocalRead⁡k-BPTISP(2O(S(n)),S(n)).\operatorname{LocalRead}_k\text{-BPSPACE}(S(n)) := \operatorname{LocalRead}_k\text{-BPTISP}(2^{O(S(n))}, S(n)).

In particular,

LocalRead⁡k-BPL:=LocalRead⁡k-BPSPACE(O(log⁡n)).\operatorname{LocalRead}_k\text{-BPL} := \operatorname{LocalRead}_k\text{-BPSPACE}(O(\log n)).

An immediate question is whether locally read-kk randomized machines can be simulated with read-once access to randomness while approximately preserving their acceptance probabilities and attaining a small asymptotic space bound, particularly when kk is constant.

Our Results

We show the following simulation of read-kk space bounded PTMs by read-once space bounded PTMs.

Theorem 1.3 (Fresh-Coin Simulation). Let kk, TT, S:N→N≥1S : \mathbb{N} \to\mathbb{N}_{\ge1} be logspace constructible functions. Let MM *be a locally read-*k machine running in time O(T(n))O(T(n)) and space O(S(n))O(S(n)) on every input and every random tape. For every 0<ε≤1/20 < \varepsilon\le1/2, there exists a probabilistic TM M′M' with a read-once random tape such that, on every input xx of length nn, the output distributions of M(x)M(x) and M′(x)M'(x) have total variation distance at most ε\varepsilon. Moreover, M′M' runs in space

O(k(n)2(S(n)+log⁡(n+T(n)))+log⁡(1/ε))O\left(k(n)^2(S(n)+\log(n+T(n)))+\log(1/\varepsilon)\right)

and time

1ε⋅2O(k(n)2(S(n)+log⁡(n+T(n))))\frac{1}{\varepsilon}\cdot2^{O(k(n)^2(S(n)+\log(n+T(n))))}

on every random tape.

For constant kk, this yields the following equality of complexity classes.

Corollary 1.4. For every constant integer k≥1k \ge1 and every logspace constructible function S(n)≥log⁡nS(n) \ge\log n,

LocalRead⁡k-BPSPACE(S(n))=BPSPACE⁡(S(n)).\operatorname{LocalRead}_k\text{-BPSPACE}(S(n)) = \operatorname{BPSPACE}(S(n)).

In particular,

LocalRead⁡k-BPL=BPL⁡.\operatorname{LocalRead}_k\text{-BPL} = \operatorname{BPL}.

Other Related Read-kk Models

Several related models restrict repeated access in different ways. A kk-pass random-tape machine scans the same random string at most kk times, typically resetting its random head between successive left-to-right scans. David, Papakonstantinou, and Sidiropoulos [7] studied the applicability of Nisan’s generator to such multipass models; Mandal, Pavan, and Vinodchandran [19] investigated their derandomization, and Dixon, Mandal, Pavan, and Vinodchandran [DMPV16] studied their advice complexity. We note here that since the local read-kk model can move their random tape heads freely, it can definitely simulate the k′k'-pass model, by setting k=2k′k = 2k'. However, before this work, it is highly unclear how to simulate local read-kk model by k′k'-pass models, as even for constant kk, a straightforward simulation of read-kk models may need Θ(n)\Theta(n) passes. Another extensively studied model is the read-kk oblivious branching program. Here the variable queried at each layer is fixed independently of the input, and each variable occurs at most kk times in this reading sequence. The sequence may jump arbitrarily between variables; there is no adjacent-cell head. Gurjar and Volk [12] constructed pseudorandom generators for read-kk oblivious branching programs when the reading sequence is known to the generator, and Doron and Lang [5] subsequently improved the seed-length bounds. Knowledge of the reading order is a separate issue even for read-once programs, as illustrated by the unknown-order generator of Forbes and Kelley [9]. More general read-kk branching programs allow the next queried variable to depend on the current state.

Technical Overview

Let MM be a locally read-kk randomized Turing machine running in time TT and space SS on inputs in {0,1}n\{0,1\}^n. For every 0<ε≤1/20 < \varepsilon\le1/2, we will construct a randomized Turing machine M′M' with one-way access to its random tape. On inputs in {0,1}n\{0,1\}^n, the machine M′M' runs in space

O(k2(S+log⁡(n+T))+log⁡(1/ε))O(k^2(S + \log(n+T)) + \log(1/\varepsilon))

and time 2O(k2(S+log⁡(n+T))/ε2^{O(k^2(S+\log(n+T))}/\varepsilon. For every x∈{0,1}nx \in\{0,1\}^n, the acceptance probabilities satisfy

∣Pr⁡[M′(x) accepts]−Pr⁡[M(x) accepts]∣≤ε.\left|\Pr[M'(x)\text{ accepts}] - \Pr[M(x)\text{ accepts}]\right| \le\varepsilon.

Decomposing executions using checkpoint transitions Fix an input xx. We may assume k≤T+1k \le T + 1. Let J0={1,…,T+1}J_0 = \{1,\ldots,T+1\} contain all random-tape positions that M(x)M(x) may read. A visit is a maximal consecutive stay at a single random-tape cell. Because MM is locally read-kk, once the head leaves a cell after that cell’s kk-th visit, it can never return to that cell. Consequently, the rest of the computation is confined to the side of the departed cell on which the head remains.

This observation lets us shrink the interval of accessible cells. Start with I=J0I = J_0. In the remaining execution, consider the first departure that terminates the kk-th visit to some cell v∈Iv \in I, and mark that departure. If the computation continues, replace II by the connected component of I∖{v}I \setminus\{v\} that contains the head immediately after this departure, and repeat the same rule. The marked departures therefore split the execution into a nested sequence of intervals, each obtained from the previous one by removing a single cell and keeping the side containing the head.

The retained interval alone does not determine how the simulation should continue, since some bits inside the interval may already have been read. We therefore also record the execution’s boundary history: the chronological list of crossings of the interval’s boundary, together with their times, positions, and configurations (control state, input- and work-tape head positions, and work-tape contents). Given an assignment to the bits in the interval, we can reconstruct each portion of the past execution inside the interval from the recorded crossings that enter the interval, and we can check the reconstructed execution against the recorded crossings that leave it.

A checkpoint D=(ID,HD)D=(I_D,H_D) consists of two objects. The interval IDI_D is the retained interval immediately after the marked departure, that is, the connected component of I∖{v}I\setminus\{v\} containing the head after it leaves vv. The boundary history HDH_D is the chronological list of all crossings of the two boundaries of IDI_D, from the start of the computation through the marked departure, together with their times, positions, and configurations. We form the checkpoint at this departure, before the head begins its next visit. At that moment every cell in IDI_D has been visited fewer than kk times: before the departure, every cell in I∖{v}I\setminus\{v\} had been visited fewer than kk times, and ID⊆I∖{v}I_D\subseteq I\setminus\{v\}. Since each boundary of IDI_D is crossed O(k)O(k) times, the history HDH_D has list size at most O(k)O(k). A checkpoint transition is the passage from one checkpoint to the next, or from a checkpoint to the point where the computation stops.

Executions inside an interval. To carry out the consistency checks recursively, we simulate the computation inside an interval while using recorded crossing information to skip the intervening computation outside it. An execution constraint CC on an interval JJ specifies an initial configuration, random-head position, and time; prescribed bit values and crossing histories; and boundary tables specifying exits from and returns to JJ.

For a fixed assignment u∈{0,1}Ju\in\{0,1\}^{J}, let Exec⁡r(C,u)\operatorname{Exec}_{r}(C,u) denote the stopping report of the following deterministic execution. Starting from the initial data specified by CC, the execution follows MM inside JJ, using uu for random reads and checking the requirements of CC. Each exit from JJ is handled by the boundary tables. When the boundary checks pass and a return is supplied, the execution skips the external computation and resumes at the prescribed configuration and time. The visit counts inside JJ are not reset when the execution returns to JJ. An attempted (r+1)(r+1)-st visit causes overflow before the new visit is counted or its bit is read.

The execution stops at the first normal termination, overflow, or failed check. Its stopping report ρ\rho records the configuration, head position, time, and reason for stopping, together with the details of a failed check when applicable. The requirements of CC are checked during execution; the assignment uu need not satisfy them in advance.

Distributions of transitions between checkpoints. Let 2≤r≤k2\leq r\leq k and let C∈ErC\in\mathcal{E}_r be an execution constraint on an interval LL, where the families Er\mathcal{E}_r are defined in § 3.4 and include child constraints constructed from incorrect guesses. For each assignment u∈{0,1}Lu\in\{0,1\}^{L}, let D0,D1,…,DmD_0,D_1,\ldots,D_m be the successive checkpoints encountered by the constrained run of CC with visit threshold rr, where the start of the execution is the initial checkpoint D0=(L,())D_0=(L,()). Let ρ=Exec⁡r(C,u)\rho=\operatorname{Exec}_r(C,u) be the corresponding stopping report. The next outcome after DjD_j is Oj=Dj+1O_j=D_{j+1} if j<mj<m, and Om=ρO_m=\rho.

Let ULU_L be uniform over {0,1}L\{0,1\}^{L}. Drawing uu according to ULU_L induces a distribution on checkpoint paths and stopping reports. For a checkpoint DD with Pr⁡UL[Dj=D]>0\Pr_{U_L}[D_j=D]>0, define

KjC,r(D,o):=Pr⁡UL[Oj=o∣Dj=D].K_j^{C,r}(D,o):=\Pr_{U_L}[O_j=o\mid D_j=D].

References

  1. [1]Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science (FOCS), pages 218–223. IEEE, 1979. 1DOI
  2. [2]Allan Borodin, Stephen Cook, and Nicholas Pippenger. Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and Control, 58(1–3):113–136, 1983. 1DOI
  3. [3]Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, and Ilya Volkovich. Launching identity testing into (bounded) space. Electronic Colloquium on Computational Complexity, Report TR24-041, 2024. 2
  4. [4]Kuan Cheng and Ruiyang Wu. SC derandomization for regular ROBPs and models beyond BPL, 2026. Preprint, September 2026. 2arxiv.org/abs/2609.23603
  5. [5]Dean Doron and Yonatan Lang. Improved pseudorandom generators for read-k branching programs. Electronic Colloquium on Computational Complexity, Report TR26-210, 2026. 4
  6. [7]Matei David, Periklis A. Papakonstantinou, and Anastasios Sidiropoulos. How strong is Nisan’s pseudo-random generator? Information Processing Letters, 111(16):804–808, 2011. 4DOI
  7. [8]Abraham D. Flaxman and Alan M. Frieze. The diameter of randomly perturbed digraphs and some applications. Random Structures & Algorithms, 30(4):484–504, 2007. 2
  8. [9]Michael A. Forbes and Zander Kelley. Pseudorandom generators for read-once branching programs, in any order. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), 2018. 4arxiv.org/abs/1808.06265
  9. [10]John Gill. Computational complexity of probabilistic turing machines. SIAM Journal on Computing, 6(4):675–695, 1977. Preliminary version in STOC 1974. 1
  10. [11][GV04] Dan Gutfreund and Emanuele Viola. Fooling parity tests with parity gates. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 3122 of Lecture Notes in Computer Science, pages 381–392. Springer, 2004.
  11. [12][GV20] Rohit Gurjar and Ben Lee Volk. Pseudorandom bits for oblivious branching programs. ACM Transactions on Computation Theory, 12(2), 2020.arxiv.org/abs/1708.02054
  12. [13][Hea08] Alexander D. Healy. Randomness-efficient sampling within NC¹. Computational Complexity, 17(1):3–37, 2008. Preliminary version in RANDOM 2006.DOI
  13. [14][Hoz21] William M. Hoza. Better pseudodistributions and derandomization for space-bounded computation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 of Leibniz International Proceedings in Informatics, pages 28:1–28:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.
  14. [15][INW94] Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pages 356–364, 1994.DOI
  15. [16][KV85] Marek Karpinski and Rutger Verbeek. There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator. Information and Control, 67(1–3):158–162, 1985.
  16. [17][KV86] Marek Karpinski and Rutger Verbeek. On the power of two-way random generators and the impossibility of deterministic poly-space simulation. Information and Control, 71(1–2):131–142, 1986.
  17. [18][KvM02] Adam R. Klivans and Dieter van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing, 31(5):1501–1526, 2002. Preliminary version in STOC 1999.
  18. [19][MPV15] Debasis Mandal, A. Pavan, and N. V. Vinodchandran. On probabilistic space-bounded machines with multiple access to random tape. In Mathematical Foundations of Computer Science 2015, Part II, volume 9235 of Lecture Notes in Computer Science, pages 459–471, 2015.
  19. [20][Nis92a] Noam Nisan. RL ⊆ SC. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pages 619–623, 1992.
  20. [21][Nis92b] Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992. Preliminary version in STOC 1990.DOI
  21. [22][Nis93] Noam Nisan. On read-once vs. multiple access to randomness in logspace. Theoretical Computer Science, 107(1):135–144, 1993.
  22. [23][NZ96] Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43–52, 1996. Preliminary version in STOC 1993 under the title More Deterministic Simulation in Logspace.DOI
  23. [24][Ope26] OpenAI. Exact derandomization of logarithmic space: L = RL = BPL. OpenAI Math Release, September 2026. Preprint, September 23, 2026.

Paper details

vlnc:W_xm58drdj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents