Derandomization of Logarithmic Space: Inside OpenAI’s Bold L = RL = BPL Breakthrough Claim
Randomness is a useful shortcut in computing. A few coin flips can help a memory-starved algorithm explore possibilities without recording every step. For decades, theoretical computer scientists have asked whether those random bits provide genuine extra power when an algorithm has almost no working memory. OpenAI says the answer is no. In a 108-page manuscript … Read more