← All problems

BPL = L (Derandomizing Bounded-Error Logspace)

Prove or disprove that every language decidable by a probabilistic Turing machine using O(log n) workspace, polynomial time, and bounded two-sided error is decidable by a deterministic Turing machine using O(log n) workspace.

Source: Kuan Cheng and Ruiyang Wu, Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions, Introduction.

Status Open Status review date not recorded in this edition

Listed by ProofAtlas. Status qualification is attributed to ProofAtlas; no full resolution is certified here.

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 1

Claimed by OpenAI.See full solutionHide full solution

This manuscript claims exact derandomization of polynomial-time randomized logarithmic space: L = RL = BPL.

GitHub repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Exact-Derandomization-of-Logarithmic-Space-L-equals-RL-equals-BPL-September-23-2026/paper.pdf

  • OpenAI-103-01-Exact-derandomization-of-logarithmic-space-L-RL-BPL.pdf1,000,094 bytesOpen