solved where we knew that there existed a guaranteed polynomial time algorithm for

linear programming. And then it was decades later before those algorithms were

brought to the point where they could compete with simplex in practice. but it

happened. that was a problem, we didn't know whether there was a polynomial time

algorithm for many, many years even though people were trying to find it. but with

articulating this division in the theory helped with the idea of let's get, let's

find a polynomial time algorithm and someone did. and so, that's was certainly

difficult to bring that about, but it happened. And then, you might say, well

that gives some hope that we could do others. But actually for integer linear

programming, you just take linear programming and restrict the variables to

have zero or one values, or Boolean satisfiability. nobody knows a polynomial

time algorithm. And, in fact, few people believe that a polynomial time algorithm,

guaranteed polynomial time algorithm exists for these problems. But, we still

don't know for sure. that's the topic of today's lecture. Now, all of these things

are examples of search problems. and we characterize them this way cuz it's an

intuitive way to describe really the problems that we want to solve. so the

idea is that the problem has, lots of problem instances, its input. and what you

want to do in a search problem is find a solution, or report that there's no

solution. so, there's just one requirement. And the requirement that

distinguish, distinguishes a search problem from just any problem is that we

have to be able to efficiently check that the given solution is in fact the

solution. Say, in that efficiently in this lecture means in poly, guaranteed

polynomial time in the size of the input. And for the problems that I just gave

they're definitely search problems. because just take a look at what they are.

So, for LSOLVE, the problem is input instances are just systems of linear

equations. So, matrix of N squared numbers, N N + one numbers. And solution

is just three numbers. And to check the solution, just plug in the values to

verify each equation so that's certainly polynomial time in the size of the input.

So, LSOLVE is a search problem. And similarly, LP is a search problem. LP

characterized in this way. you've got a system of linear inequalities and you're

given a solution, you can efficiently check that, that solution satisfy those

inequalities. These satisfiability problems are all search problems. In

interlinear programming, you have the inequalities. you get values that are zero

or one. You can plug them in the equations and check. That's what characterizes a

search problem. It's got a small solution that we can efficiently check whether it's

a solution and satisfy the same. You've got the truth values, you've got the

equations and then you plug in values and verify each equation. now, what we're

doing is distinguishing search problems from other kinds of problems that are very

similar. And actually, the theory works for these other kinds of problems. One

kind is called a decision problem where it's just problems that have a yes, no

answer. in, another one is optimization problems which are problems of where you

want to find the best solution in some sense like linear probic, programming or

shortest path. but the theory that we're about to lay out all the major conclusions

hold for any one of these classes of problems. it's just that it's best to fix

on one to make sure that there's no holes in any of the statements that we make. so

we're doing that at the outset with the search problem. Now, and, and, and so you

can imagine so if one way to check that if you have a problem that finds a solution

to a linear programming problem, you can specify it in such a way that it's a

decision block. Is there a solution that satisfies another given inequality linear,

combination of the value's less than a certain value? And then you can use binary

search or something to do the, the final m aximiza, minimization for linear program,

programming, and so forth. There's all kinds of way to move among these problems.

But we're going to focus on search problems. so here's another one factor. so

given an inv, integer, find a nontrivial factor,. might find, it might take a lot

of computation to try to find a factor. but if somebody gives you a factor, then

all you have to do is long divide. So again, factor is a search problem. so

those are some examples of the basic types of problems that we're foing to consider

when we investigate intractability.