Hello and welcome to the next module of the Advanced Algorithms and Complexity class. This module is devoted to reductions. Reductions allow us to say that one search problem is at least as hard as another search problem. Intuitively, the fact that a search problem A reduces to a search problem B just means that we can use an efficient named the polynomial time algorithm for the problem B to solve the problem A, also in polynomial time. And we can use it just as a black box. Pictorially, the fact that the search problem A reduces to search problem B means that we have the following pipeline. Assume that we have an instance, I, of a problem, A. Now we are going to design an algorithm that solves the instance I using an algorithm, a polynomial-time algorithm for B as a black box. For this reason, it is shown here in a black box. Okay, the first thing to do is that we need to transform an instance I into an instance I of the problem A, we must enter an instance of the problem B. We do this by calling an algorithm f. So we plug, we feed the instance I of the problem A into the algorithm f, and it gives us the instance f(I) of the problem B. We then use the algorithm for B as a black box to solve it efficiently, and it gives us one of two outputs. Either there is no solution for this instance f(I). In this case, we report that there is no solution also for i, for the instance i of the problem A. Otherwise, it gives us a solution S for instance f(I). In this case, we need to transform it back to a solution of I. We do this by using the second algorithm h. And it transforms in solution f(I) into solution h(S) of the initial instance I. We can now state it formally. Given two search problems, A and B, we say that A reduces to B and write A to B, if there is a pair of two polynomial time algorithms f and g. The algorithm f transforms any instance of A into any instance f(A) of the problem B, such that the following holds. If there is no solution for the instance f(I) of the problem B, then there is no solution for the instance I of the problem A. Otherwise, if there is a solution S for the instance f(I), then by applying the algorithm h to this solution S, we get a solution h(S) of the initial instance I. Now when we have an option of reduction, we can imagine a huge, huge graph containing all search problems. So this graph can respond to the class NP of all search problems. In this graph, there is a vertex for each search problem and to put an edge between the search problem A and the search problem B a direct approach, if a search problem A reduces to search problem B, okay? Then by definition, we say that this search problem is NP-complete if all other search problems reduce to it. Pictorially, it looks as follows. So the red vertex here corresponds to an NP-complete search problem. So in some sense, this problem attracts all other search problems, all other search problems reduce to it. But it otherwise an algorithm for an NP-complete problem can be used as a polynomial time algorithm for an NP-complete can be used as a black box to solve just all other search problems also in polynomial time. It is not at all clear that such NP-complete problems exist in our graph of all such problems, but we will show that they do exist. And we will show, actually, that all the search problems that we've seen in the previous modules, namely satisfiability problem, travel analysis problem, the maximum independence set problem, longest pass problem, integer linear programming problem, they are all NP-complete. Namely, if you design a polynomial time algorithm for any of them, you will solve just all search problems in polynomial time.