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.
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.
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 solution
This manuscript claims exact derandomization of polynomial-time randomized logarithmic space: L = RL = BPL.
GitHub repository: https://github.com/openai/math
- OpenAI-103-01-Exact-derandomization-of-logarithmic-space-L-RL-BPL.pdfOpen