Abstract

Randomised algorithms are the simplest and fastest known solution to many decision problems. We reason about randomised algorithms using the concept of probabilistic Turing machines, which are a variant of nondeterministic Turing machines that have probabilistic transition choice.

This talk is aimed as a discussion around the various complexity classes associated with randomised computation (BPP, RP, ZPP ). I shall start by presenting these classes, alongside known relationships between them and complexity classes studied in the Part IB course (P, NP).

We will then see how randomised algorithms provide much more efficient solutions than deterministic ones by looking at the Schwartz-Zippel lemma applied to Polynomial Identity Testing, which gives a polynomial time Monte Carlo algorithm, as opposed to its deterministic counterpart, which is exponential.

In conclusion, I shall discuss the open problem of P = BPP and the usage of pseudorandom number generators to deterministically simulate randomised algorithms.