Probabilistic Computation
Probabilistic computation will now be described.
In order to make this formal, yet another variant of a Turing machine — a probabilistic Turing machine — will be introduced. This will be used to define a variety of complexity classes involving algorithms that decide membership in languages, using at most polynomial time — but which are “randomized” and can fail in a variety of ways.
Technical results explaining why it is generally believed that these complexity classes do not include NP-complete languages will be described (but not proved).
