Design and Analysis of Algorithms

Randomized and Approximate Algorithms 537

Exercise Let A be a BPP algorithm that accepts x ∈ L with probability atleast 3/4, and accepts x ∉ L

with probability at most 1/4. Show that if we run the algorithm A for t independent iterations and return the

majority answer, then the error probability becomes at most 2

–O(t)

.

Note that both RP and co-RP are subsets of BPP. An important open question in complexity theory is

whether BPP ⊆ NP or not.

19.4 APPROXIMATE ALGORITHMS

We shall now discuss NP-hard optimization problems, Inapproximability and Analysis of Approximation

Algorithms.

19.4.1 NP-Hard Optimization Problems

Many of the algorithms in this world deal with optimization. Some of these problems can be solved exactly

in polynomial time. Other ...