Comment by vlovich123
10 hours ago
Funny you mention probabilistic algorithms. If I’m not mistaken one of the OpenAI results is that most of the probabilistic methods (specifically those that use a logarithmic amount of space)-4 have non-probabilistic versions that are as efficient in time and space (L = RL = BPL)
> most of the probabilistic methods (specifically those that use a logarithmic amount of space)
These are by far not most, nor most of the practically useful ones. Directed graph reachability, given an adjacency list as input, is NL-hard.