We now arrive at the heart of the discussion, the definition of the complexity class NP as computational problems where you can efficiently recognize the solution, roughly the same thing is problem solvable is in good force search. The idea of NP completeness, that the problem can be as hard as any other problem, where you can efficiently recognize a solution, the ubiquity of NP-complete problems, including possibly a problem you're working on right now in one of your own projects, and what should be part of your toolbox, a simple recipe for proving that problems are NP-complete. We left off the last video noting that the travelling salesmen problem by virtue of being solvable in the exponential time using brute force search is certainly not as hard as notorious problems like the halting problem. So, perhaps we can instead of mass evidence of interactability for the TSP by showing it's as hard as any other problem solvable using brute-force search, that is every other brute-force search solvable problem reduces to solving the traveling salesman problem. To turn this idea into mathematics we have to identify the minimal ingredients necessary to solve a problem using brute force search. And the key idea turns out to be the efficient recognition of purported solution. [SOUND] Specifically, we say that a computational problem, like, say the traveling salesman problem, or frankly almost any other problem we've talked about in these classes is a member of the complexity class NP if it meets the following two criteria. The first property is sort of a simple prerequisite. It is search that solutions have length polynomial in the input size. The second property, and this is really the key one, is that if someone offers up to you a purported solution to a NP problem, you can verify its correctness in polynomial time. To make sense of this abstract definition, let's think about some concrete examples. Let's start just with the traveling salesman problem. So, consider the instance of the traveling salesman problem that's specified by some n vertices and distances amongst all of the pairs of vertices. And suppose we want to know whether or not there's a tour that has a total length. At most one thousand. So, let's for the moment set aside the problem of checking whether or not one of the n factorial tours does indeed have cost of at most 1000. Let's instead think about the much more modest question, of whether or not a single proposed tour has cost at most 1000. Well, that computational problem is to verify whether or not a single suggested tour meets the target or not. That's an easy computational problem, right? The tour is specified just by order in which you're supposed to visit the vertices. The length of that ordering is certainly polynomial in the length of the input, and all you gotta do is add up the n edges that gets traversed in this tour, and check if this sum is at most 1000 or not. This argument shows that checking whether or not there exists a tour, with total cost and most sum threshold, does indeed belong to the complexity class NP. Right, you can write down a purported solution, in polynomial length. All you need to do is specify the ordering, and you can verify whether or not a candidate solution, whether or not a proposed tour meets the threshold in linear time, just by adding up the corresponding edge costs. If it bothers you that I moved away from the problem of computing an optimal, minimum cost tour, and studied instead the seemingly easier problem, I'm just checking, does there exist a tour that has total cost at most a given threshold, notice that the former problem reduces to Multiple indications of the latter problem, just by binary search over the threshold. The same reasoning can be applied to pretty much all the computational problems we've seen in these courses, placing all of them into the complexity class NP. So for the types of problems we've been thinking about, solutions can generally be specified in linear space, correctness can be verified in linear time. Another genre of problems that we haven't really discussed in these classes, but are important in the application domains, and are also canonical NP problems are constraint satisfaction problems. In general in a constraint satisfaction problem you have a bunch of variables. The simplest case would be binary or Boolean variables. And then you have a list of constraints, and each constraint specifies for a subset of the variables. a permitted list of configurations of those variables. So one simple case which some of you've seen and if you study NP completeness property you'll definitely see it will be the three set problem. The three set problem does indeed consider Boolean variables, so each variable xi can either be zero or one and you can think of the clauses as forbidding a single assignment to a triple vertices. So a clause might say you are not allowed to simultaneously assign. X3 to 1, X5 to 0, and X8 to 1. So clauses for big particular triples of assignments, and the question then is, does there exist an assignment of all of the variables to 0 an 1, that simultaneously satisfies all of the constraints. These kinds of constraint satisfaction problems also belong to the complexity class in p. So here if you have a purported assignment of all of the variables to values that meets all of the constraints, well you can write it down very simply just the value for each of the variables. And it's easy to check. I just iterate through the constraints one at a time and see if yes indeed, the values that you're suggesting for the variables in that constraint are on the list of permissible value combinations. At the beginning of this video, I suggested that the complexity class NP would represent problems that are brute force solvable, in the same way that the traveling salesman problem is. If you look at the actual definition I just gave you of the class NP, it's in terms of efficient recognition of solutions, but let's now observe that this definition NP, in terms of efficient verification of purported solutions does indeed imply that these problems can be solved in exponential time using brute-force search. So really, all you do here is check each of the candidate solutions one at a time. And in doing so, you see very clearly the role of the two properties in the definition of an NP problem. The role of the first property saying solution length has to be a polynomial in the input size, in turn, restricts the number of possible solutions, the number of bit strings of that given length, to be at most, exponential in the input size. The second property of course assures you that for each of those only exponentially many possibilities, you can verify whether or not it is a correct solution, whether or not it's a short TSB tour, whether or not it's a satisfying assignment to some variables in a constraint satisfaction problem in polynomial time. Now because the requirements for the class NP are so weak, the class NP is very big, where all membership in NP requires essentially as the ability to officially recognize the solution. You know one when you see one, and as you can imagine, that property is met by many of the computational problems that we ever think about. Factoring almost any graph problems you'd ever think about, sequencing problems, most constraint satisfaction problems, and so on. As we've said, it's true that not every, natural computational problem, is NP. The halting problem is an extreme example. That's in fact undecidable, there's no algorithm at all. There's also some natural problems and some application domains which are neither in NP, nor they undecidable. So, model checking is one domain that furnishes lots of examples of problems strictly harder than NP. The vastness of the complexity class NP means that NP-completeness is strong evidence of intractability. Remember what it means for a problem to be complete. For some set of problems, it means it's as hard as any other problem in that set. Every other problem in that set reduces to the complete problem. Therefore, suppose you had a polynomial time algorithm for just one, NP-complete problem, you would get, automatically, by the definition of a reduction, a polynomial time algorithm for every single computational problem in NP. Every single problem for which you can efficiently recognize a solution. That is, solving just 1 NP-complete problem in polynomial time would imply that NP is the same as P. Every problem in NP can be solved in polynomial time. It's pretty hard to really grok all of the ramifications of this kind of result, if P were to equal NP. So, just as one example, modern e-commerce, as we know it, would fall apart like a house of cards. That's because it depends on the security of crypto-sysytems, like RSA, which in turn assumes the computational intractibility of problems like factoring. Yet, an efficient algorithm for even the most obscure NP-complete problem, would automatically imply, imply, at least in principle, a polynomial time algorithm for factoring. So this provides a satisfying resolution to a narrative we began in the previous video. Recall, we were discussing the traveling salesman problem. And, like thousands of other people, we were wondering whether or not there was a polynomial time algorithm for it or not. For example, Edmunds conjectured, in '65, that there is no polynomial time algorithm for it. Now I've, obviously what you really want is, the answer. You either want a proof of Edmund's conjecture, that there's no efficient algorithm for TSB, or, even more astonishingly, you'd want a polynomial time algorithm that solves the problem. But we also have to face the reality that we may not know the answer for sure to this question, for quite a while. Years, certainly. Decades, probably. Centuries, who knows, maybe. So the challenge then for people thinking about algorithms and computation, is to nevertheless devise a theory which usefully differentiates tractable problems from relatively intractable ones, even in the face of this massive deficiency of our understanding of what is possible and what is impossible. And the brilliant way out is relative difficult as now personified by NP-completeness. If you want to amass extremely strong evidence of the computational intractability of a problem, prove that it's MP complete. Prove that a polynomial time algorithm for the problem, if it existed, would solve thousands upon thousands of unsolved computational problems.
