I wish we had a theory connecting randomness with time/space complexity. Intuiti... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		novaRom on May 17, 2024 \| parent \| context \| favorite \| on: Computer scientists invent an efficient new way to... 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 on May 17, 2024 [–]

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

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact