[MUSIC] In the last lesson you saw from Christine that coming up with an optional solution for the traveling salesperson problem using brute force method can be fairly difficult. And in this lesson beginning this lesson we're gonna start looking at the similar detail. So by the end of this video you should be able to explain the value and limitations to be able to classify a problem as being NP Hard. So let's go back to where we were at the end of Christine's lesson. So, what we saw is a brute force solution traveling salesperson is N factorial in terms of run time. And N factorial is super scary, because as the problem size gets bigger you just can't solve it anymore. Even at an N of 19 this is gonna difficult, and by an N end of say 23 different cities you're trying to solve a traveling sales person problem for this is really not solvable anymore. So what do we do now? We know that the brute force method doesn't work very well. What should we do? Now we may be thinking we should think really hard and try to come up with some better solution to this problem, and often times that's actually a pretty reasonable approach. But in this case I'm gonna tell you that's actually probably not a good idea. In fact it could be quite futile to take that approach. And to understand why that's the case we have to get into an area of computer science known as Complexity Theory. Now Complexity Theory is a huge area of computer science. It deserves a specialization itself. I'm just gonna give you some brief details about it. Which apply toward traveling sales person problem. What happens within Complexity Theory is we attempted to classify problems by their inherent difficulty. So let's take a couple of problems that we've solved before. So searching Linked List we know is O(n), sorting an array we know is, or we think is O(n log n). n Matrix-Matrix Multiply right now is something like O(n to the -2.3), so these are all problems. And can we classify them as being related to each other is one more difficult than the other? And essentially all of these problems could be put into the classification of polynomial time solvable. So we can take all these problems, put these all into one classification, and this classification just says that all of these are solvable in O(n to the k). And k can be something really big here, but it's still better than something say k to the n. Now that's a really big scary thing. But n to the k a little less scary, and that would be within polynomial time. So the question then is are there other kinds of classifications that are more difficult then say those that are in polynomial time. And there's one fairly well known classification known as nondeterministic polynomial time, or NP. Now we can spend a whole bunch of time diving into a nondeterminism versus determinism. It's a fairly complex topic. It's a lot of fun, but it's beyond really the scope of this course. So I'm gonna talk a little bit of a high level about what we mean by saying a problem is an NP. Now what we're really trying to say is that some problems seem harder to find solutions than those that are NP, but if you happen to have a solution handy someone gave it to you through an Oracle you could actually check its correctness pretty easily. That's what it means to be essentially in NP. Now again I said we believe this. NP is believed it contain problems harder than P. And when I say wait a second that pretty wish washy. Don't we know? Well no we actually don't. So this is one of these really classical problems in computer science. Does P equal NP? Are these two classifications the same? It's unknown. It's one of the Millennium Prize Problems. In fact if you could solve this you got a million dollar prize associated with it. More importantly than a million dollar prize If you could show that P is not equal to NP you'd essentially confirm what a lot of computer scientists already suspect, but if you could show that P equals NP you'd essentially change the field instantly. You'd be incredibly powerful and it's a great topic. But now that we have this notion then of P versus NP let's try to expand our classifications just a little bit to talk more, to eventually get back to the traveling salesman problem. So beyond NP-Complete we also have a classification known as NP-Hard. Now within NP-Hard problems these are problems are least as difficult to solve as those with in NP. Now what's neat is if you can come up with a polynomial time solution with any NP-Hard problem you could actually solve all problems in NP kind of instantly. It's pretty amazing. So why then are we talking about Complexity Theory? How does this relate back to our traveling salesperson problem? Well it relates back because traveling salesperson is within these classifications. So the original traveling salesperson problem that Christine described is a traveling salesperson optimization problem. And by optimization what I mean is we're going to try and find a solution that has the minimum distance. Hence the optimization piece. It has to have the minimum distance. We can also write our traveling salesperson problem just slightly differently to make a decision problem, which is is there a solution that has a distance less than L. So does this solution take less than say 2000 miles to accomplish. Now these seem very similar and they are incredibly similar in terms of trying to find a solution, but they were very different in terms being able to check whether or not a solution is actually correct or not. So if you're trying to check whether or not the solution for the NP complete decision problem is right or not all you do is just check the distance of path that someone gave you. Does it actually visit all the cities? And does it have a distance less than L? If it does we're done. That's pretty easy to check, but if someone gave you a solution for the optimization problem well you could check that it visits all the cities, but does it have the minimum distance? Well I don't know I'd have to compare against all other possible paths. And now that get's hard again. So the TSP optimization problem as we've describe it is actually an NP-Hard and the decision problem is an NP-Complete. So these are essentially considered hard problems. And it may not only be difficult to try to solve this in polynomial time it may be impossible. So to spend your time trying how the polynomial time solution for this may not be the best use of your time. The good news here is the story doesn't end here, and the next video we'll talk about what we can do next.
