not speedup exists, and settling this question is likely to be as hard as the notorious ? problem of complexity theory.

There is a weaker sense in which probabilistic algorithms currently offer advantages over deterministic ones. There exist problems for which the fastest known algorithm is probabilistic and problems for which at present the fastest fully analyzable algorithm is probabilistic. Here the situation reflects the current limitations on our knowledge. Section 4.3 describes examples of such problems from number theory, i.e., primality testing and factorization. In both cases, at present, the best fully analyzed algorithms are probabilistic ones.

Probabilistic algorithms give a demonstrable speedup in the exchange of information among several people, each having partial information to begin with. This is the subject matter of communication complexity. It plays an important role in distributed computing, in which exchange of information among the processors is an important part of the computational task. Communication complexity results are described in §4.4.

The theoretical possibility of speedup has been formalized in computational complexity theory with the notion of probabilistic complexity classes; these classify computational problems according to the running times and types of error allowed by probabilistic algorithms. Here we define several of these complexity classes.

The model of computation used is a probabilistic Turing machine. This is a Turing machine that has an extra "random" tape containing a random string of zeros and ones that can be read as necessary. A probabilistic polynomial-time Turing machine (PPTM) is such a machine equipped with a clock that, when given an input of n bits, always halts after p(n) steps, where p is a fixed polynomial. The performance of such machines is averaged over the uniform distribution of all random bits read by the machine. (At most, p(n) random bits are read during the computation on an n-bit input.) The computational problems considered are those of recognizing a language , where {0, 1}* denotes the set of all finite strings of zeros and ones. For example, might consist of all prime numbers, expressed using their binary representations.

We say that is in the complexity class BPP (bounded-error-probability polynomial time) if there is a PPTM that, given , outputs