Lecture 2. Solving problems using Boolean circuits, probabilistic circuits

In this lecture, we discussed how to formulate solutions to computational problems using Boolean circuits. A language $L$ belongs to the complexity class $\mathtt{P}$ if there exists a uniform family of Boolean circuits such that the Turing machine generating this family runs in polynomial time. We looked at a couple of examples of solutions to simple problems in terms of explicitely constructing uniform families of Boolean circuits. We also began discussing probabilistic computations. Probabilistic Boolean circuits are Boolean circuits in which uniformly random bits are allowed. Using randomness sometimes makes it possible to solve computational problems more efficiently.