To get started, we're going to introduce the idea of search problem which
encompasses many of the fundamental problems that we want to try to solve. so
here's a familiar problem from secondary school, we'll call it LSOLVE. So, the
problem is, given system of linear equations find a solution. so, we've got
simultaneous equations involving the variables x1, x0, x1, and x2, and what we
need to do is find a solution. In this case, these three equations have the
solution x0 = -one, x1 = two, and x2 = two.
If you plug those values in for x0, x1, and x2 and those equations, they, you'll
find that they satisfy those equations. in, in secondary school you learn how to
solve those with Gaussian elimination or eliminate a variable at a time. so that's
LSOLVE. now, last time we talked about linear program, programming. and that's a
similar problem that you can almost cast as the following given a system of linear
inequalities, you know, find a solution. Actually for LP we do a little bit more
because we also try to optimize. But, this is a fine characterization of a way to
formulate the problem. So now, we just have inequalities. and again, there's a
solution. actually, the first part of the computational burden in linear programming
is to know whether there's a solution or not before you can even apply the simplest
method. so we in this case, there is some equations on the left, and on the right
there's values that if you plug those values into those equations, they satisfy
it. So, that's minor inequalities of satisfiability. here's another one.
suppose that again we have inequalities but suppose that we insist that the
variables be zero or one. and actually, this is a special case of linear
programing that comes up to be useful as a model in many situations where the
variables modeled as I say, what's going on in an electronic circuit or maybe other
situations where we just did want, want them to be zero or one. And we had an
example of this when we were talking about bipartite matching reduction to linear
program, programming. so that's in this case, you take those equations, those
inequalities and you put in those values. And sure enough, x1 + x2 is bigger than
one, x0 + x2 is bigger to the one but the, the some of the three of them it's less
than or equal to two, so that's a solution. and this is just one more so
those are all called satisfiability problems. So, you have a bunch of
equations, with variables. And you have values for the variables. And you want to
know if the variables satisfy the equation. and the simplest satisfiability
problem is the one that just uses Boolean values. given a system of Boolean
equations where the variables are either true or false, and then the equations are
just made up of or an and connective in the presentation. And, and you, you're
checking whether in a bunch of when an expression involving truth values is true
or false in the prime means not. So, not x1 or x2 and x0 or x2 equals true. that's
going to be true in that case. that's going to be satisfied in that case because
x1 equals false, so not s1 is true. So the first term is true here. not x1 is true so
that, or whatever is true. and then this term here, x0 or x2, x2 is true. So, both
those terms are true and we're adding them, so it's true. And you should go
through and check each of the equations to make sure that those truth values satisfy
those equations. So, those are fundamental problems. They're very similar in nature.
and there's lots and lots of applications where people want to find efficient
solutions for these problems. so the question is, how do these things fit into
our theory? Which of these have algorithms that are guaranteed to run in polynomial
time? When you look at the problems, they didn't look really all that much
different. well, for LSOLVE, we have Gaussian elimination and other ways to
solve Gaussian elimination works in n cubed time or end of three halves time
where n's the size of the input. but what about the other ones? do they have
polynomial time algorithms? well, LP I mentioned briefly at the end of the last
lecture. yeah. It was proven but actually was open for decades. It wasn't until
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.