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.