Okay, so next we'll look at what the idea of the classes P and NP mean in terms of actual problems we're looking at solving. we want to classify our problems the same way as which scientists classify elements. And the key technique they're going to, that we're gonna use is reduction. So the problem that we're gonna start with. That is, the key to this theory is the Boolean satisfiability problem. and we talked about at the beginning, it's not that different than Gaussian than systems linear equations. It's just that everything has to be Boolean variables. and so. given a system of boolean equations, find a solution. and. Even on it's own, it's a very significant problem. it Has come, it comes up, and, and people solve huge and, and face huge satisfiability problems in trying to understand whether trying to prove whether software, to verify software, that software works correctly. Also, hardware for design automation. people model what's going on with huge satisfiability problems and solve them. it's, it's so basic that it even arises in, in, in physics, and scientific studies, and. The so-called, mean field diluted spin class model. It's a very fundamental, problem that is just, about, logical reasoning about what's going on, in, in some complex system. now the question is, so it's a search problem. we know that and what that means is that if we have a solution, we can efficiently check that we have a solution But the question is, is it in P? Can we find an algorithm that guarantees to find a solution in polynomial time? Now people solve huge problems be, but in some sense maybe they're lucky because the instances that they're trying to solve don't cause the algorithm to run in polynomial time. But the real question is can we guarantee that we'll get that in polynomial time? So, well. What do we do? Well. For satisfy ability, as I mentioned, it's pretty easy to use. Exhaustive search, just try all the truth assignments. and really what that means is, they have an algorithm that if doesn't find the right tru th assignment it might wind up trying all of them. but you might find on earlier and that's, that's what happens with practice. but the big question is, can we do anything that is really substantially more clever than sat? then, then the brute force algorithm. that, that is an algorithm run brute force in the, in the worst, worst case. That's a, that's a pretty stringent definition of substantially. but that's the one that we're that we're talking about. can we get less than exponential, worst case performance. And some people have worked on this for long enough now to, that most people agree that there's no polynomial time algorithm for SAT. To start classifying problems, what we're going to do is kind of adopt that as an assumption. Or at least we'll classify problems according to the difficulty of, of SAT. And what that means is we're going to use reduction from SAT. So if we reduce SAT to some problem. as we talked about in the reduction layer, lecture. That means if we could solve this problem efficiently, we also could solve that efficiently. And we're going to, call, a problem like that intractable. if we could solve it efficiently we could solve SAD efficiently. We don't think we can solve SAD efficiently. that problem's intractable. So that's, that's our meaning of the word intractable. Alright, so now what are we gonna do to classify problems? So, the first thing is which search problems in, in P, so there's no really easy answer for that except for, devising algorithms. but we do have this reduction technique that is gonna help us It's, now we can be a little more general than when we were actually designing algorithms that we we're gonna use and we can have the reduction take polynomial amount of time before we're insisting on linear time. And not only that, we can. Take a polynomial number of calls to the, the one that we're reducing to. And again all this is about is that if you have a polynomial time algorithm for y then the reduction gives you a polynomial time algorithm for x. And we're just try ing to have the most general definition that preserves that property. and so the consequences that if we have a polynomial time reduction from SAT to a given problem Y, then we can conclude that Y is well, it's intractable. By our definition. that is it's as difficult as SAT and we think that there is no polynomial time algorithm for it. So that's a mean tool that we're going to start out with to use for classifying problems so let's look at an example. Actually you can work with simpler versions of, of SAT. You can actually reduce any SAT problem to just a form where you have a bunch of equations using literals . so, usually we use and so for example like that. So, given that fact to find a solution. so, now we have another problem IOP given a system of linear inequalities find a solution. So, what we want to do is, Characterize sat as an ILP problem. So, that is, if we had an efficient solution to ILP, it'd give us a solution to sat. So let's take a look at, this example. so our, whatever SAT problem we have, we put it in this form. and now, we're gonna introduce a variable, C1. and, for every, literal in the SAT problem. we're gonna, put C1 greater than or = to, either the literal, if it's not negated. Or one minus the literal if it is negated. so in this case, . And so we have C1 greater or = to one - x1. Greater than x or greater than x3, like that. and then we're going to have a fourth inequality. that says that it has to be less than or equal to the sum of those three. so what this construction does is if the equation is satisfied, if there's some way to satisfy this equation then it's going to be C1 equals to one. so that is, if there is a way to, make each one of these terms one, say by setting X1 to zero, X2 to one and X3 to one, then this thing will be, those things all will be true. and then this one also will be true. And all four of these are true. If and only if, the equation is satisfied. And we make a little group like that for, all four of the equations. and then we do a, a similar thing wi th a variable that's true if and only if, all of the c's are true. So this one's, this variable has got to be less than all four of these. And the only way that this thing's gonna be one, is if all the equations are satisfied. So this system, has a solution. if and only if, there's a SAT solution. And from the solution to the system, you can find the SAT solution. So that's a reduction from SAT to integer linear programming, programming. Because of this reduction, we feel that we don't, we're not gonna have a polynomial time solution to integer linear programming. If we did, we'd have a fast solution to SAT. so that's, that's an important, piece of knowledge where you focus on this one hard problem that we know about, and that tells us another problem, is that, the, the reduction tells us another problem that is at least as hard. and that by itself is interesting integer linear programming is a very important computation with lots of applications. but the a, amazing thing that was shown by Dick Carp in the 70s, is that there are lots and lots of problems that you can reduce satisfiability to. and actually you. Car produced SAT to the so called independent set problem then reduce that one to aisle P, but if you do two reductions it still, it still works. if, I could solve ILP quickly. I could solve independent set quickly. Then, I could use that to solve SAT quickly. so, if you can prove any problem on this set, you can reduce any problem on this set. To your new problem that's like proving that SAT reduces to it. So, if we adopt the idea that SAT is intractable it means that all of these problems are intractable. These are lots of important problems that people were looking for solutions and couldn't find good solutions to, and, what Karp shows in the Travelling Salesman problem and the Hamilton Path problem which is the like problem. Finding the that's the problem of finding a path on the graph that visits all the vertices. So what, what Karp showed is that all of these problems are intractable. They're all as least as difficult to SAP, as SAP. if we had a efficient polynomial times solution to any one of them, we'd have a polynomial time solution to SAP. that was Quite a powerful idea of using polynomial time reduction to classify problems in this way. In fact, it's such a powerful idea that nowadays there's maybe 6000 papers per year. with reductions from some problem that has, been shown to reduce from SAT to some new problem. and these are, important problems in, all fields of human endeavor. so, for example, the so called protein folding problem. Which, in biochemistry, where, people are trying to understand what's going on, in, living organisms. has been reduced from SAT. We'd like to solve that problem. But, and that would help us understand what's going in, in living organisms. much better. but if we had a, an efficient solution for, a guaranteed polynomial time solution to that problem. We'd have a, a, a, guaranteed polynomial time solution to SAT. and so we don't think so, Or, economics, With, if you just make the arbitrage problem a little more complicated and a little more realistic. where, there's, a little cost involved with doing things. it turns out to be, that, you can't have an efficient solution. Not to that one unless, cause it would imply an efficient solution to SAP. and many, many other examples. Voting power and politics. Experimental design and statistics. Thousands and thousands of papers per year involving reductions from sap. Very, very powerful concept, that the idea of reducing from sets. Now, we have two ways to classify problems. We can, find a polynomial time algorithm and then we know problems in P, or we can develop a polynomial time reduction from set and that'll prove that at least if you believe that sat is difficult you should believe that'll be difficult to find a solution to your problem. so that's the first step in classifying problems.