Now when have a formal definition of the search problem and when we've seen a few example of search problems, we are ready to state the most important open problem in computer science. The problem about classes P and NP. So recall once again that the search problem is defined by an algorithm C that takes an instance I and a candidate solution S, and checks in time polynomial in I where the S is indeed a solution for I. In other words, we say that S is a solution for I if and only if the corresponding algorithm C of I and S returns to, then the class NP is defined just as the class of all search problems. The name of this class stands for non-deterministic polynomial time. This essentially means that we can guess a solution and then check its correctness in polynomial time. That is a solution for a search problem can be verified in polynomial time. The Class P on the other hand, contains all search problems that can be solved in polynomial time. That is all such problems for which we can find a solution in polynomial time. So to summarize, once again the class P contains all search problems whose solution can be found efficiently. This class contains in particulars, as minimum spending 3 problems. The shortest path problem, the linear programming problem, the independent set on trees problem. The class NP contains all the problems whose solution can be verified efficiently that is given an instantiation solution for this instance solution, we can check in polynomial time. In the size of this instance, whether this is indeed a solution for. This class contains such problems as a problem, the longest path problem, problem and independent set on general graphs. The main open problem in computer science asks whether these two clauses are equal, namely whether the clause P is equal to the clause NP. This is also known as the P versus NP question. The problem is open, namely we do not know whether these two clauses are equal and this problem turns out to be very difficult. This is a so-called Millenium Prize Problem. There is a $1 million prize from Clay Mathematics Institute for resolving this problem. Note that if P is equal to NP, then all search problems, I mean all the problems for which we can efficiently verify a solution, they can be solved in polynomial time. In other words, for all the problems for which we can efficiently verify a solution, we can also efficiently find a solution. On that hand, if P is not equal to NP, then there are search problems for which there are no efficient algorithms. So there are problems like, for example, problem for which we can quickly check whether a given candidate solution is indeed a solution, but there is no polynomial time algorithm for finding such a solution efficiently. At this point, we do not know whether P is equals to NP or not, I mean, where they are such problems for which there are no polynomial time algorithms. In the next part, at the same time we will show that all the problems that we mentioned in this lecture namely the problem, the longest path problem, the traveling salesman problem, the inter linear programming problem are in some sense, the most difficult search problems in the class NP.