Today we show how to reduce the error probability of probabilistic algorithms, prove Adleman’s theorem that polynomial time probabilistic algorithms can be simulated by polynomial size circuits, and we give the definition of the polynomial hierarchy
1. Adleman’s Theorem
Last time we mentioned that if we start from a randomized algorithm that provides the correct answer only with probability slightly higher than half, then repeating the algorithm many times with independent randomness will make the right answer appear the majority of the times with very high probability.
More formally, we have the following theorem.
Theorem 1 (Chernoff Bound) Suppose are independent random variables with values in and for every , . Then, for any :
The Chernoff bounds will enable us to bound the probability that our result is far from the expected. Indeed, these bounds say that this probability is exponentially small with respect to .
Let us now consider how the Chernoff bounds apply to the algorithm we described previously. We fix the input and call over all possible random sequences. We also define the independent 0/1 random variables such that if and only if outputs the correct answer.
First, suppose . Then the algorithm outputs the right answer , when . So, the algorithm makes a mistake when .
We now apply the Chernoff bounds to bound this probability.
The probability is exponentially small in . The same reasoning applies also for the case where . Further, it is easy to see that by choosing to be a polynomial in instead of a constant, we can change the definition of a algorithm and instead of the bound of for the probability of a wrong answer, we could equivalently have a bound of or , for a fixed polynomial .
Would it be equivalent to have a bound of ?
Definition 2 is the set of problems that can be solved by a nondeterministic Turing machine in polynomial time where the acceptance condition is that a majority (more than half) of computation paths accept.
Although superficially similar to , is a very powerful class; (polynomial time computations with an oracle for ) includes all of , quantum polynomial time , and the entire polynomial hierarchy which we will define later.
Now, we are going to see how the probabilistic complexity classes relate to circuit complexity classes and specifically prove that the class has polynomial size circuits.
Theorem 3 (Adleman)
Proof: Let be in the class BPP. Then by definition, there is a polynomial time algorithm and a polynomial , such that for every input
This follows from our previous conclusion that we can replace with . We now fix and try to construct a circuit , that solves on inputs of length .
Claim 1 There is a random sequence such that for every is correct.
Proof: Informally, we can see that, for each input of length , the number of random sequences that give the wrong answer is exponentially small. Therefore, even if we assume that these sequences are different for every input , their sum is still less than the total number of random sequences. Formally, let’s consider the probability over all sequences that the algorithm gives the right answer for all input. If this probability is greater than , then the claim is proved.
The probability in the second expression is the union of possible events for each ; this is bounded by the sum of the probabilities
So, we proved that at least half of the random sequences are correct for all possible input . Therefore, it is straightforward to see that we can simulate the algorithm , where the first input has length and the second , by a circuit of size polynomial in .
All we have to do is find a random sequence which is always correct and build it inside the circuit. Hence, our circuit will take as input only the input and simulate with input and for this fixed . Of course, this is only an existential proof, since we don’t know how to find this sequence efficiently.
In general, the hierarchy of complexity classes looks like the following picture, if we visualize all classes that are not known to be equal as distinct.
It is, however, generally conjectured that , in which case the complexity map greatly simplifies:
2. Complexity Classes with Advice
In this section we prove an alternative characterization of classes of functions computable by bounded-size circuits.
Let be a function (e.g. ).
Definition 4 is the class of decision problems such there is a sequence of strings where , and a polynomial-time algorithm such that correctly solves the problem.
Proof: For any problem in , there is an algorithm A and a sequence of strings that can solve it. For inputs of length n, we can construct . Such set of circuits will solve the problem.
For any problem in , there is a family of circuits that solves it. Consider constructing a circuit evaluation algorithm .
3. Polynomial hierarchy
Remark 1 (Definition of and ) A problem is in if and only if there is a polynomial time computable and a polynomial time bound such that
is the class of problems whose complement (switch YES-instance to NO-instance) is in . Formally, a problem is in if and only if there is a polynomial time computable and a polynomial time bound such that
The polynomial hierarchy starts with familiar classes on level one: and . For all , it includes two classes, and , which are defined as follows:
Definition 7 is the class of all problems such that there is a polynomial time computable and k polynomials such that
Definition 8 is the class of all problems such that there is a polynomial time computable and polynomials such that
One thing that is easy to see is that . Also, note that, for all , and . These subset relations hold for as well. This can be seen by noticing that the predicates do not need to “pay attention to” all of their arguments, and so can represent classes lower on the hierarchy which have a smaller number of them.
Exercise 1 has a complete problem.
Next time we will prove (a stronger version of) the following result:
Theorem 9 If , then , .