 Randomized algorithms

The algorithms studied so far in this section have been deterministic; such algorithms follow the same execution path (sequence of operations) each time they execute with the same input. By contrast, a randomized algorithm makes random decisions at certain pomts in the execution; hence its execution paths may differ each tune it is invoked with the same input. The random decisions are based upon the outcome of a random number generator. Remarkably, there are many problems for which randomized algorithms are known that are more efficient, both in terms of time and space, than the best known deterministic algorithms.

Randomized algorithms for decision problems can be classified according to the probability that they return the correct answer.

• 2.75 Definition Let A be a randomized algorithm for a decision problem L, and let I denote an arbitrary instance of L.
• (i) A has О-sided error if P(A outputs YES | 7’s answer is YES ) = 1, and P(A outputs YES | 7’s answer is NO ) = 0.
• (ii) A has 1-sided error if P(A outputs YES | I’s answer is YES ) > 7, and P(A outputs YES | 7’s answer is NO ) = 0.
• (iii) A has 2-sided error if P(A outputs YES | 7’s answer is YES )>§ , and P(A outputs YES | 7’s answer is NO ) < |.

The number ^ in the definition of 1-sided error is somewhat arbitrary and can be replaced by any positive constant. Similarly, the numbers § and i in the definition of 2-sided error, can be replaced by | + e and e, respectively, for any constant e, 0 < e <

2.76 Definition The expected running time of a randomized algorithm is an upper bound on the expected running time for each input (the expectation being over all outputs of the random number generator used by the algorithm), expressed as a function of the input size.

The important randomized complexity classes are defined next.

• 2.77 Definition (randomized complexity classes)
• (i) The complexity class ZPP (“zero-sided probabilistic polynomial time”) is the set of all decision problems for which there is a randomized algorithm with О-sided error which runs in expected polynomial tune.
• (ii) The complexity class RP (“randomized polynomial time”) is the set of all decision problems for which there is a randomized algorithm with 1-sided error which runs in (worst-case) polynomial time.
• (iii) The complexity class BPP (“bounded error probabilistic polynomial time”) is the set of all decision problems for which there is a randomized algorithm with 2-sided error which runs in (worst-case) polynomial time.
• 2.78 Fact P C ZPP C RP C BPP and RP C NP