4 ms·

I wish we had a theory connecting randomness with time/space complexity. Intuitively I think the key to many computational limitations is making use of randomn

I wish we had a theory connecting randomness with time/space complexity. Intuitively I think the key to many computational limitations is making use of randomness.

ilya_m 2y ago
Your intuition is correct. See https://en.wikipedia.org/wiki/BPP_(complexity) https://en.wikipedia.org/wiki/BPP_(complexity)