Okay. We're going to finish up by talking a little bit about different approaches to dealing with needing to solve intractable problems. this, actually, a lot of different ways to proceed when you run into an intractable problem. One idea is to exploit it. In fact, an example of this, a very successful example of this is modern cryptography. People using the internet for commerce, or for interaction through digital signatures and other mechanisms are absolutely relying on modern cryptography for security and privacy. and that's all based on the RSA cryptosystem, or much of it. and it's based on the idea that multiplying two N-bit integers is relatively easy. This and a, brute force multiplication algorithm gets it done in quadratic time when there's faster ways. So that's polynomial time. So in order to encrypt something, you need to multiply things, but in order to break something, you would need to factor things. That's exploiting interactability. Nobody knows a good way to factor. A factor is not MP complete, by the way, not known to be MP complete. So it doesn't, in fact, not quite as hard as other problems. But still nobody knows a fast way. So but this is an example of exploiting suspected problems, that's suspected to be intractable. In fact, there's other ways to make money [UNKNOW put, put some challenges and go ahead and factor this number towards $30,000. . Some of these things have been , prices have already been claimed but it may be easier to go after this than after the, the millionth and actually [UNKNOWN] and Idilin were just not just but professors at MIT when they came up with this and they realized that. the important commercial potential of this And actually created a company based on the difficulty of factoring that sold for 2.1 billion dollars not that long ago. And it's the basis for, internet commerce. so these possibilities for making a lot of money out of, understanding the difficulty of computation, are not imaginary. they're quite real. so, I, talk briefly about the complexity of fac tors. That's, another problem like, LP is that, it's current status is what LP was in the 70s. we're using it, a lot of people were doing it we knew that the worst case was of simplex was exponential. we'd like to classify it, like to know if there's a poly time, nomial time algorithm, but nobody knew one. And then the big surprise for LP was that Catching came up with a, a polynomial time algorithm and, and, then, you know, and people went to work. For factor we're kind of in the same situation. It's NMP. Being as we saw, it's just a, search problem but. , it's not known or believed to be either NP or NP complete. But again who knows. so what if it turns out that P equals NP. so, so that would mean that now it factors in P and that would . It's not just the math. that would mean, there'd be an easy way to break the, RSA crypto system which is in wide use. people could, break codes by, just by factoring. and that, that would not be a good thing for the modern economy. actually, something that attracted a lot of attention, although it's almost twenty years ago now. was a result by Peter Shore that said, that, There's a device, not quite a real device, called a quantum computer. At least one that you can imagine building that solves factoring in polynomial time. So that raises the question of, do we still believe the extended Church-Turing thesis. There are plenty of people that are not so sure and are working hard on trying to build devices that might have a big impact on this kind of theory. well, actually we create, and has created a, a new theory based on how difficult is it to do things with these sorts of devices. Okay, but in general, suppose you have a intractable problem, what are you going to do to cope with it? Well, there's a number of things that people have done really successfully. so remember what it means to be intractable. so a problem's intractable if, in, in, in the sense that we don't know a polynomial time problem that's guaranteed to solve any instance. Now so maybe you can give up on, on, on e of the three key features of that statement. maybe we don't care if we can solve every possible instance. Maybe it's only the instances that are gonna arrive in the real world, arise in the real world that matter. so or maybe you can even simplify the problem and that's the one that you really need to solve. So for example, if you restrict. Satisfiability to have at most two literals per equation, can solve in linear time. Or even if you just insist that there be at most one of the literals per equation be not negated. That's called a Horn-SAT. There's a linear time algorithm for that. So maybe your problem is you're trying to solve too hard a problem, and you can come up with a more special case of the problem that's actually the one you want to solve that you could solve. So that's definitely one way to cope with interactability. another thing is optimality. we've been talking about search problems but this is, this is more a statement about Mm-hm, . But, optimization problems, we're looking for the best solution or we're looking for a proximate solutions. where you take away the guarantee that the solution's perfect in some way. So for example, the traveling sales person problem. People can find ways to get tours that are close to the best possible tour, but maybe not the best. And there's many, many other example of this. Where people are looking for good solutions, without trying to guarantee that they're optimal. And those, maybe those solutions are very close to optimal, or at least, close enough that you can use the solution and move on. if you understand the quality of the solution that you have, that might be, good enough. But and again, the idea of approximation algorithm and where you really can prove what the quality is. So for example there's a max three set that guarantees to satisfy seven-eighths of the clauses. And, actually these algorithm they're really coming at the fine line between what's tractable and intractable. And so, for example the, if you want to do 7/8's plus anything then it mea ns that P equals MP, if you can do that in polynomial time P equals MP there are lots and lots of amazing results of this sort out there. but anyway, in practice relaxing condition, that you find the perfect solution sometimes can get a long way in practice. and then the other thing is guaranteed polynomial time. We're talking about worse case behavior. but there's solutions out there. for example, there's a SAT solver that was done here at Princeton that can solve 10,000 variable SAT instances. Or, as we, as I mentioned, there's solvers out there for integer linear programming that will solve huge instances of real world problems. Worst case behaviour may be observed in a real world, might even be hard to find real world problems. This is, definitely a lot of room here, to not find solutions that, might be efficient for the class of problems, that you want to solve. and I just want to finish up with one of the most famous NP complete problems which is the so-called Hamilton path problem. and so that's given a graph, you want to find a path that visits every vertex exactly once. And simple path, so I can't reuse any edge. So that's a solution to the Hamilton Path probelem for this graph. Another way to characterize it is a longest path problem, longest simple path problem in a graph. If you have one of visit every edge eactly once, that's not difficult. It's actually in the book. But Hamilton path is NP complete. that's a natural problem that's MP complete. and actually this is it's empty incomplete, but here's a really simple exponential time algorithm for computing the Hamilton path. it's just our depth for search algorithm where we mark nodes and recursively go through all the edges all the vertices adjacent to the current vertex. and if they're not marked, go ahead and visit them recursively, marking all the nodes that we see. The only difference from the depth first search, is this thing here. Where, when we're done, with our recursive call on a node we, unmark it. And what that does is make this code try a ll possible paths. And there's an exponential number of paths. so, so define program for doing it for small graphs. But it's going to take exponential time for big graphs. But the longest path problem is NP complete, and we're going to finish up with a, a, a song that was composed by a John Hopkins student, one time when he was having trouble, thinking about this idea. Woh, oh, oh, oh, find the longest path. Woh, oh, oh, oh. Find the longest path. Woh, oh, oh, oh. Find the longest path. If you said P is NP tonight, there would still be papers left to write. I have a weakness, I am addicted to completeness. And I kep searching for the longest path. The algorithm I would like to see is of polynomial degree. But it's elusive, nobody has found conclusive evidence that we can find a longest path. I have been working for so long. I swear it's right, and he marks it wrong. Some how I'll feel sorry when it's done, GPA 2.1 is more than I hope for. Gary, Johnson, Karp and other men (and women too). Tried to make it order N log N. Am I a mad fool if I spend my life in Grad School, forever following the longest path. Woh, oh, oh, oh, find the longest path. Woh, oh, oh, oh, find the longest path. Woh, oh, oh, oh, find the longest path. that's a fine sentiment on which to end this class on algorithms. I hope that all of you out there are inspired to face the computational challenges of the future with the algorithms and the concepts that you've learned in this class. so, that's all. Keep searching, so long.