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.
Topic revision: r3 - 10 Jul 2017, AndrasTobias
 
  • Printable version of this topic (p) Printable version of this topic (p)