\text{BPP} \subseteq p / poly Remember the advice-taking TM formulation of circuits. Now, a language L \in \text{BPP} if \exists a polytime TM M such that: x \in L implies P\left[M\left(x, v\right) \text{ accepts}\right] \geq \frac{2}{3} x \not\in L implies P\left[M\left(x, v\right) \text{rejects}\right] \geq \frac{2}{3} Intuition: we want to use r as advice. But, we need a “random” advice for each x which we don’t have. But; consider the following parameterization of BPP: we notice that if we have \frac{1}{3} chance of “bad” advice, we know that we can bump the failure down by trying a more, trending towards 2^{-O\left(k\right)}. Using O\left(k\right), by the union bound, we know at least one advice is good for all input x. If \text{SAT} \in p / poly, then polynomial hierarchy collapses to the second level; that is pi2=sigma2 Suppose \text{SAT} \in p / poly, so \exists a polysize circuit family:

preliminaries 1: satisfying assignments Recall that SAT has a poly-time search-to-decision reduction—suppose \text{SAT} \in P, there is a poly-time truing machine M such that given \phi, outputs the actual satisfying assignment. The same thing works for circuits: there exists a poly-time transformation using circuits such that, given:

it outputs: either reject or an actual satisfying assignment (through a multi-output circuit). preliminaries 2: \pi_{2} \text{SAT} This is \pi_{2} complete:

using our condition, let’s now describe a \Sigma_{2} algorithm that decides \pi_{2} \text{SAT} Recall by the first preliminary and the given, we have a self-certifying circuit family in p/poly (that runs in polynomial size (circuits)). We desire to build a poly time TM A such that: