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.