OctoInformBeta

Exact derandomization of logarithmic space: $`\mathsf L=\mathsf{RL}=\mathsf{BPL}`$

A randomized machine has a finite control, a read-only input between two endmarkers scanned by finitely many read heads, finitely many binary work tapes, and one fresh fair coin bit at each step. Such a machine is deterministic when its moves do not depend on the coin bits. It works in logarithmic space when the number of distinct work cells it visits on an input of length nn is O(log⁡(n+2))O(\log(n+2)). Its acceptance probability on an input at step tt is the probability, over the coin bits, that it has accepted by step tt. A language is a set of binary words. The class 𝖫\mathsf{L} consists of the languages decided by deterministic logarithmic-space machines that halt on every input. The class 𝖱𝖫\mathsf{RL} consists of the languages AA for which some logarithmic-space machine halts within c(n+2)kc(n+2)^k steps on every input of length nn, for constants c>0c>0 and kk, and has acceptance probability at step c(n+2)kc(n+2)^k equal to 00 on inputs outside AA and at least 1/21/2 on inputs in AA. The class 𝖡𝖯𝖫\mathsf{BPL} is defined in the same way, with acceptance probability at most 1/31/3 on inputs outside AA and at least 2/32/3 on inputs in AA. The question is whether 𝖱𝖫\mathsf{RL} contains a language outside 𝖫\mathsf{L}.

Gill developed the complexity theory of probabilistic Turing machines. Aleliunas, Karp, Lipton, Lovász and Rackoff asked explicitly whether polynomial-time randomized logarithmic space can be simulated in deterministic logarithmic space. The pseudorandom generator of Nisan uses a seed of O(Slog⁡R)O(S\log R) bits for a space-SS computation reading RR random bits. Nisan later simulated bounded-error randomized logarithmic space deterministically in polynomial time and O(log⁡2n)O(\log^2 n) space simultaneously. Saks and Zhou reduced the deterministic space needed for bounded-error logarithmic-space computation to O(log⁡3/2n)O(\log^{3/2}n). Hoza improved this space bound to O(log⁡3/2n/log⁡log⁡n)O(\log^{3/2}n/\sqrt{\log\log n}). Reingold placed undirected connectivity in deterministic logarithmic space.

The preprint proves that 𝖫=𝖱𝖫=𝖡𝖯𝖫\mathsf{L}=\mathsf{RL}=\mathsf{BPL}. It also proves that, for a logarithmic-space randomized machine that halts within c(n+2)kc(n+2)^k steps on every input of length nn, for constants c>0c>0 and kk, a deterministic algorithm given an input xx of length nn and a precision qq in unary approximates the acceptance probability of the machine on xx at step c(n+2)kc(n+2)^k to within 2−q2^{-q} in space O(log⁡(n+2)+q)O(\log(n+2)+q) and time (n+2)O(1)2O(q)(n+2)^{O(1)}2^{O(q)}; the Lean library does not contain this result.

The Lean library Logspace proves that 𝖫=𝖱𝖫\mathsf{L}=\mathsf{RL} and 𝖱𝖫=𝖡𝖯𝖫\mathsf{RL}=\mathsf{BPL} for the classes defined above. It takes no hypothesis. Each result on these pages is the Lean library’s, stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every one of them, so the Lean library is the reference. Where the preprint states a result differently, its statement is given beside the Lean library’s. The preprint is a guide only, which gives the results their order and their names.

The Lean library: Logspace

Logspace is a Lean library: 24 items, in nine groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. §1 (setting): the machine model and the classes L, RL, BPL Coin-flipping machines and the three logarithmic-space classes. §1
  2. Theorem 1.1 [Exact logarithmic-space derandomization] Randomized logarithmic space equals deterministic logarithmic space. §1
§2. The transition model and resource parameters 1 item
  1. Lemma 2.1 [Configuration reduction] Configuration graphs of clocked machines form a correct first stage. §2
§3. Rank channels for retained vertex sets 1 item
  1. Lemma 3.1 [Rank-channel estimates] Retention estimates for rank channels. §3
§4. The exact correction and copy hierarchy 8 items
  1. §4 (setting): stage inputs, the cutoff Q and the correction iteration Stages and their corrections through a shoulder cutoff. §4
  2. Lemma 4.1 [Fixed point and factorial truncation] Corrected iterates increase in factorially small steps. §4
  3. Lemma 4.2 [Elementary pilot bounds] Corrections of a bounded forward matrix stay bounded and forward. §4
  4. Lemma 4.3 [The detector bounds overloaded columns] Heavy rows raise the detector and light rows bound it. §4
  5. Lemma 4.4 [Residual bounds and unsigned-term domination] The corrected residual is substochastic and dominates its unsigned terms. §4
  6. Proposition 4.5 [One-stage density and active-count reduction] Splitting into copies keeps a step matrix, at rate f/16f/16. §4
  7. Remark 4.6 [Order of the one-stage constants] The one-stage constants of the copy hierarchy exist. §4
  8. Proposition 4.7 [Reward identity and a shallow target] The reward identity survives the prize step. §4
§6. Conditional averaging in the shared environment 3 items
  1. Lemma 6.1 [A uniform affine spectral gap] The sampler’s generators have a uniform spectral gap. §6
  2. Lemma 6.2 [Conditional averaging] The mean over the hit set factorizes and the sampled average mixes. §6
  3. Lemma 6.3 [Validated walk variants] The guessed variant performs the conditional generator step. §6
§9. Adaptive fingerprints within budget blocks 2 items
  1. Theorem 9.8 [Error bounds for the actual estimators] Under its hypotheses the estimator meets its error contract. §9
  2. Lemma 9.9 [Restoring equality test] An equality test that restores its catalyst register. §9
§11. Uniform controller implementation 2 items
  1. Theorem 11.1 [Realization of the estimator interfaces] Recursive controllers with stack budgets run in logspace. §11
  2. Lemma 11.5 [Inverse contour] The contour walk of an indexed forest is reversible. §11
§12. Derandomization and quantitative consequences 2 items
  1. Theorem 12.1 [Fixed inverse-polynomial accuracy] A close logspace estimate places bounded-error languages in L\mathrm{L}. §12
  2. Lemma 12.2 [Conditioning on one start] Errors at the retained start are at most 1/321/32. §12
Lean results with no numbered counterpart 3 items
  1. Two interleaved trials Two interleaved trials square a halting machine’s rejection probability.
  2. Polynomial clock of deterministic logspace deciders Deterministic logspace deciders halt in polynomial time.
  3. A register-program criterion for L Languages decided by register-computable expressions are in LL.

No item matches.