In this part, we will discuss a general way of proving that a particular search problem is NP complete. Well, as you know already, we are going to prove NP-completeness via reductions. And there are two equivalent ways of using reductions, namely we say when we know that A reduces to B. We know that if the problem B is easy, namely if there is an efficient that is polynomial time algorithm for B, then the results are an efficient algorithm for A. This is just by definition, right? We know that A reduces to B, that is an efficient algorithm for B can be used as a black box for solving A. So if B is easy, if they research an algorithm, then we can use it to solve A in polynomial time. The second way of using reductions is just a counter positive of the first item here. If A reduces to B and we know that A is hard, meaning that there is no polynomial time algorithm for this problem then also there is no polynomial time algorithm for B. Then B is also hard. Indeed if B was easy then A was easy, right, as shown in the first item. So B cannot be easy in this case. There cannot be a polynomial time algorithm solving B. When proving MP completeness of certain such problems, we will use the following basic fact about reductions. Namely, that reductions do compose. More formally, if a search problem A reduces to search problem B, and In turn search problem B reduces to search problem then A reduces to C. Let's prove this formally. The fact that A reduces to B means that we have a pair of polynomial time algorithms f sub AB and h sub AB. Namely F transforms any instance of a problem A into any instance of a problem B. And hAB transforms any solution to problem B and back through a solution of problem A. And similarly for the reduction from B to C. Okay, and then to construct such a pair of algorithms to reduce problem A to problem C, we just compose the corresponding function. So, assume that we have an instance IA of the problem A, and we need to get an instance of a problem C. For this, we first apply the algorithm fAB to the instance IA, this gives us an instance of the problem B. We then apply the algorithm fBC to the resulting instance of the problem B. This gives us an instance of the problem C. The important thing to note here is that the resulting composed algorithm has polynomial time. To see this note that, assume for example that the running time of the algorithm fAB is for example P(n) and its running time is n cubed for example. And the running time of the algorithm f sub AB is q of n and it is n to the 5. Then the running time of the composed algorithm is p(q(n). This is p(n) to the 5, and this is in turn n to the 5 cubed, which gives us n to the 15. Namely, when you compose two polynomial functions, you get also polynomial function. Which justifies that the running time of this algorithm is also polynomial. To get an algorithm which transforms the solution to C back through the solution of A, you just apply the combination of the correspondent to each algorithm. Namely, when you get a solution S sub C for the problem C, you first apply the algorithm hBC. This gives you a solution back to the problem B. Then you apply the algorithm h of AB to transform it back to a solution of the problem A. Pictorially, this composition of reductions means the following. Whenever we have these two pair of edges in our graph of all problems of the class NP. We also have the following edge, right? So once again if A reduces to B and B reduces to C, then A reduces to C. In other words, if there is an edge from A to B and from B to C, then there is an edge from A to C. Yeah, so simple. This allows us to prove NP-completeness as follows. If we know that A reduces to B, and we know that A is NP-complete, then so is the problem B, then B is also NP-complete. Let me prove this pictorially, so this is, again, our graph, we have two problems, A and B. And we know that A reduces to B. We also know that A is NP-complete. Meaning that A attracts all other problems. In other words, there is an edge from any other problem to A. Now, since there is an edge from any other problem to A, and that at the same time, there is an edge from A to B, through the composition of reductions, we know that there is an edge from any other problem to B, right. So this is the picture that we have. B also attracts all as a problems, so by definition it is also NP-complete. Our plan for the rest of this module is the following. We will first show that the independent set problem can be reduced to a vortex cover problem. We will then show that the 3-satisfiability problem reduces to independent set problem. We will then show that satisfiability problems, a general version of satisfiability problems, reduces to its special case, namely to this re-satisfiability problem. And finally we will show that all other search problems reduce to SAT, in particular the 3 problems shown here above the satisfiability problem.