Notes on Randomized Algorithms

Randomness can help to solve problems and is a fundamental ingredient and tool in modern com-plexity theory. We assume a source of random bits. In complexity theory, we assume our source can just spit out random bits at a cost of one step per bit. Before getting into definitions let us look at some examples of randomized algorithms. 1 Promise problems Our first example will consider a problem a little different from the usual language recognition one, so we begin by discussing this new class of problems. Formally, a promise problem is a pair (P,N) where P,N ⊆ Σ ∗ are disjoint sets. The associated problem is: Input: x ∈ P ∪N Question: Is x ∈ P? The problem is specified by a set P of “positive ” instances and a set N of “negative ” instances. Given an instance x ∈ P ∪N we must determine whether it is a positive or negative instance. Note that the input is required to be in P ∪N. That’s the “promise ” in the name of the problem. An example of a promise problem is (L,L) where L is any language, and because of this, promise problems generalize problems specified by languages. Promise problems capture the fact that in practice we might know something about the distribution of input instances that enables us to preclude some instances and concentrate on others. We can extend complexity classes to consider promise problems in the natural way. For example, a promise problem (P,N) is said to be in pP if there is a TM M and a polynomial p such that for all x ∈ P ∪N • If x ∈ P then M(x) accepts • If x ∈ N then M(x) rejects • M(x) halts in at most p(|x|) steps. Here pP, “promise-P”, is a complexity class containing promise problems rather than languages. It is the promise-problem analogue of P