Lecture 2. Circuit model of computations, noisy computations

We discussed several examples of solving problems with Boolean circuits and defined complexity class $\mathtt{P}$ in terms of Boolean circuits. Then we discussed random bits and probabilistic Boolean circuits, defined the class $\mathtt{BPP}$ of languages efficiently solvable using probabilistic Boolean circuits, and proved a theorem on error reduction in probabilistic computations.