What is … BPP, RP and the other probabilistic complexity classes?
This page hosts information on Josue Tonelli Cueto's talk "What are BPP, RP and the other probabilistic complexity classes?" at the "What is …?" seminar.
Where & When
Friday, June 30, 2017, 1.00pm @ BMS Loft at Urania.
Abstract
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.