This is Josue Tonelli Cueto's talk "What are BPP, RP and the other probabilistic complexity classes?" at the "What is ...?" seminar. The talk was given on Friday, June 30, 2017, 1.00pm at Urania.
When one faces to solve problems, randomness can be used in order obtain faster answers at the cost of some uncertainty. Probabilistic complexity classes captures the different ways in which these can be done. In this talk, we introduce the basic probabilistic complexity classes, their interrelations and we illustrate by outlining the solution to concrete problems.
For more "What is ...?" seminar videos, visit whatisseminar.xyz