Now our goal is to reduce every search problem. Every problem from the class. And B, there's a Circut-SAT problem. For this consider a particular search problem A. Note that we don't even know whether the input, whether the instances of this problem are graphs or boolean formulas, or boolean circuits, or just numbers or systems of linear inequalities. The only thing that we know is that A is a search problem. So this is the only thing that we can use to construct this reduction. By definition this means that there is an algorithm C which for any instance I of the problem A and any candidate solution S in time polynomial in there. So if I check whether S is indeed a solution for I, in particular we require that the lengths of the candidate solution S must be upper bounded by the, by a polynomial of the length of I. Now a simple but crucial observation is that a computer is also a circuit. A Boolean circuit which on low level operates with beads with Boolean values. Moreover each particular computer is actually a circuit of fixed constant size, right? Now let's run our algorithm C on the inputs I and S on some computer. We know that this computer is going to perform the number of steps, which is polynomial in the size of I. Now let's replace each of these steps but as a correspondent circuit. In this case, we have a sequence of circuits such that each circuit, each of the circuits in the sequence uses the values computed by the previous circuits in this, in the secrets and compute sum values. Assume that this is a circuit responding to our computer so it uses some bits respondent to input. To instance I and some bits to respond in to the candidate's solution S. Then it computes also some values and we plug it into the second circuit and so on. We have Polynomial in many such circuit. Such circuits, polynomially in the size of I and in the end, our algorithm outputs one, if and only if S is a solution is indeed a solution for I, so while we circuit outputs 1, if S is a solution for I. So once again what we get is a circuit, which has polynomial remaining in the size, in the length of I, polynomial remaining gates, which outputs 1 if and only if S is a solution for I. Now, when we construct it as a circuit, we can use it as an input to our black box algorithm that told the circuits had problem in polynomial time, namely we do the following. Consider the circuit that we just constructed. Recall that this is a circuit cause input variables in code instances I of our such problem A and also solutions, candidate solutions. To out search problem A. And this circuit outputs one. If and only if the given candidate solution S is indeed a solution for an instance I. What I am going to do is the following. For a particular instance I, let's plug the constants for this input bits that encode this solution. What is left is a circuit, whose input variables encode different kinds of data solutions for this input instance I, and this circuit outputs one if, and only if, there is a solution for this instance I. Now we can just use our black box algorithms that solves this CircuitSAT problem to find such a solution. Great. Which means that we finally reduced our search problem A to the CircuitSAT problem. Once again, if we have an algorithm which finds a satisfying assignment for any given circuits that we can use it to solve any search problem A also in polynomial time. So the reduction is complete. To summarize, what we did is the following. We first reduced the independent set problem to the vertex cover problem. We then reduced the 3-SAT problem to the independent set problem. Then we reduced the satisfiability problem to the 3-satisfiability problem, and then we show that any, that every problem from the class MB reduces the SAT. We did this actually via the CircuitSAT problem. This ensures that all these problems here on the picture are, in fact, can be complete. That any search problem is reduced to these four problems shown here on the slide.