0:03

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

Â 1:58

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.

Â 5:51

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.

Â