Hello and welcome to the next module in which we are going to consider various ways of solving NP-complete problems. Before we proceed to actual algorithms, imagine the following situation. At your job, you are given a task to implement an efficient program that solves a certain search problem. Well, with some probability, your problem can be solved with some of the known techniques, like dynamic programming or linear programming or graph algorithms. But even if this is the case, usually it's not easy to realize this and at least it takes time. And unfortunately, this happens very rarely. So in about two weeks of trying to apply some of the known techniques to your search problem, you can always go to your boss and say, I can't find an efficient algorithm for this problem, I guess I'm just too dumb. One of the reasons why you cannot design an efficient algorithm for your problem might be just that there is no efficient algorithm for your problem. This would allow you to say to your boss, I can't find an efficient algorithm, because no such algorithm is possible. Note, however, that currently, we do not know how to prove that any search problem, but we do not have any example of a search problem for which we can prove that it cannot be solved by polynomial algorithm. In particular, if we had such a proof, we would resolve the P versus NP question. What we can do, on the other hand is to show that some search problems are the hardest search problems. So what you do is you show that your problem is the hardest one, that is you show that your problem is NP-complete. This in turn allows you to say to your boss, I can't find an efficient algorithm, but neither can all these famous people. You have proved that your problem is NP-complete. This in particular means that it is very difficult to design a polynomial time algorithm for it. But at this point, unfortunately, the problem doesn't go away. Your boss still wants you to solve it. So on one hand, you need to design an efficient algorithm for your problem. On the other hand, you know that designing such an algorithm is as hard as resolving the famous millennium prize problem, P versus NP. Should you give up at this point? No, not at all. In this module, we will learn a few techniques that allow you to solve NP-complete problems efficiently in practice. This is an outline for the rest of this module. We know already that if P is not equal to NP, then for any NP-complete problem, there is no polynomial time algorithm that finds an optimal solution in all cases. Note that there are three requirements on an algorithm in this statement. So first, we want that algorithm to have polynomial running time. Second, we wanted to return an optimal solution. In short, we wanted to do so in all cases. To solve an NP-complete problem in practice, you might want to relax one of these conditions. For example, the Zara algorithm that solves an NP-complete program in practice, but not in polynomial time, but not in all cases, but only in some cases. Such algorithms are called algorithms for special cases. So, they have polynomial times. They produce optimal solution for a problem but not in all cases, but just in some cases. Also, it is possible sometimes to design an algorithm that works in polynomial time. And in all cases, it returns a solution which might not be optimal, but it is guaranteed to be close to optimal. We will see examples of such algorithms. And finally, we can design an algorithm, which always finds an optimal solution in all cases, but we cannot prove an polynomial upper bound on its running time. But still, it works well in practice. For all these three types of algorithms, we will see examples in the next part.