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.