How do we amass evidence of computational intractability, something like the
traveling salesman problem. They key idea is through the formalism of
completeness, which in turn depends on the idea of a reduction between two
problems. We left off last video with Edmond's
prescient conjecture from 1965. In his paper Paths, Trees, and Flowers,
when, while pondering the traveling salesman problem, he conjectures that
there is no polynomial time algorithm for it.
That conjecture is equivalent, as we'll see, to a conjecture called P not equal
to NP, and this is not resolved. This remains to this day, one of the most
fundamental open problems in all of mathematics.
It's important that research in algorithms does not grind to a halt, just
because we have this open, and presumably extremely difficult, P versus NP problem
that we don't yet understand. We still want guidance about which
problems are easy, and which problems are hard.
So a pretty great idea, for giving us such guidance, guidance,
while the same time evading, actually answering the p versus np problem, is to
show that problems are difficult in a relative sense.
A mass evidence of intractability by showing that a problem is at least as
hard as, many other computational problems.
To make this idea relative difficulty precise, we need to say what we mean,
that one problem is as hard as another. The language for that is a reduction from
one problem to another. We say that a computational problem, say,
pi 1, reduces to another one, pi 2, if all you need to solve pi 1 efficiently is
an efficient algorithm for pi 2. That is, if I gave to you on a silver
platter a polynomial-time algorithm for the problem pi 2,
then using that as a subroutine, you could build a polynomial-time algorithm
for pi 1. So, we'll see some concrete examples in
just a sec, but let me just mention, I'm being slightly informal with this
definition. You'll see something a little bit more
formal if you look at a text book or take a class specifically on this topic, but
this is how you should think about reductions.
All you need to solve pi 1 is someone handing you an efficient subroutine for
pi 2. That is the algorithmic.
Way of thinking about reductions. Indeed, by virtue of being immersed in
algorithms over the past many weeks, we have examples of reductions.
The next quiz is going to ask you to recall some of them.
So the correct answer is, all of the above.
A, B, and C are all legitamite, reductions from one computational
problem, to another. So for example, answer A, this is
something we discussed back in part 1 of the course, when we first motivated
linear time median algorithms. At that point we were arguing that for a
median algorithm to be interesting, it better be faster than n log n time.
That's why we were shooting for linear time.
The reason being that one perfectly correct algorithm for computing a median
is you take the input array, you sort it, for example, using merge sort, n log in
time, and you return the middle element. That's going to be the median.
The second answer, b, so this is something we mentioned in passing, in the
naive implementation of Kruskal's algorithm, where we wanted to, check
cycles, and we were thinking about adding a new edge.
And we observed that, one way to check if a graph has a cycle, is you just run
depth first search on that graph. If there's a cycle, you'll detect it by
exploring an edge, which points backward to a vertex that you're, still in the
middle of exploring. The third example is maybe more
interesting, in the sense that we, invoke the provided sub-routine more than once.
When we first introduced the all paired shortest path problem, we observed that
one solution, and in certain cases is actually a very good solution, is to just
invoke a single-source shortest path subroutine, like Dijkstra's Algorithm or
the Bellman-Ford algorithm, n times, once for each choice of the source.
But again, it's still a reduction given an efficient algorithm, a polynomial time
algorithm. For the single-source shortest path
problem, you just run it n times, and that gives you a polynomial type
algorithm for the all-pairs shortest path.
Math problem. In fact, seasoned algorithm designers,
and seasoned programmers, are always looking for opportunities to employ
reductions. So when someone describes you a
computational problem, the very first thing you should try to think through is,
is this a problem I already know how to solve, just merely in disguise? So maybe
if you have to make sequence of decisions, maybe you can phrase it as a
shortest path problem, a problem that you already know excellent
solutions to. And if that fails, if the computational
problem you're confronted with isn't literally the same, as one you already
know how to solve, maybe by invoking known primitives, known
algorithms, a small number of times, that's efficient to solve this new
computational problem that you're confronted with.
So all of these are what I think of as honorable uses of reduction.
So somehow, the light side of the force. It spreads the frontier of ability to
cover the things we can do with algorithms wider and wider.
Now, for NP completeness, for establishing computational intractability
we have to turn this world on its head. This relies on a perverse use of
reductions, which I'll explain next. So suppose that the problem pi 1 reduces
to pi 2, in the sense that all you need, to solve pi 1 in polynomial time, is a
polynomial time algorithm for pi 2. That's the only missing piece.
Now, as algorithm designers, you're probably thinking about the happy case,
where we have a polynomial time algorithm for pi 2 sitting on the shelf.
We have something like Dijkstra's algorithm, or Bellman-Ford algorithm, and
we take it off the shelf, and we use it combined with this reduction, to solve pi
1. But, let's think about the contrapositive
of what it means when 1 problem reduces to another.
And now, lets think about the case where, we don't actually believe that it's
possible to solve pi 1 in polynomial time.
Well, if we don't think it's possible to solve pi1 efficiently, and pi1 reduces to
merely computing pi2 efficiently, well then we certainly can't believe that it's
possible to compute pi2 efficiently either.
That is, if pi 1 reduces to pi 2, and it just so happens that pi 1 cannot be
solved in polynomial time, then, pi 2 cannot be solved in polynomial time
either. So this is the perverse use of a
reduction, that I mentioned earlier. This is the dark side of the force.
Rather than using a reduction to enlarge the frontier of tractability from pi2 to
include pi1 also, we're spreading the frontier of intractability from pi1 to
pi2. So this then is what we mean formally
when we say that 1 problem is at least as hard as another.
If Pi 1 reduces to Pi 2, what does that say? It says Pi 2 allows you to solve Pi
1, maybe lets you do other stuff as well, so therefore Pi 2 is at least as hard as.
As pi 1, so we now have the vocabulary to say that 1 problem is at least as hard as
another one, and let's remember what our plan was.
Our plan was to amass evidence of the intractability of the Traveling Salesman
problem by saying it's at least as hard as lots of other stuff, so to pass from
as hard as a single. Little problem to a big set of problems.
We're going to talk about the notion of completeness.
Formally consider some set C of problems and it's going to be tricky to get the
right set of problems, we'll discuss that in detail in next video.
But for now, just let C be any old set Problems.
We call a computational problem pi complete for C.
We call it C complete, if, it's at least as hard as everything in C.
If everything in C reduces to pi. Oh, and also, this problem pi? It should
be in this class itself. So, the second constraint here is the
more important one. It's the one that fits more directly into
our narrative. Remember we wanted to, have vocabulary
for saying one problem is as hard as a whole bunch of other stuff.
C is the bunch of other stuff so, pi is at least as hard as everything in C. That
is, everything in C reduces to pi. One nice reason, to have this first
constraint also to assume that the problem pi is a member of C, is that
gives the following nice interpretation. We can think of this problem pi as being
a hardest problem in the set C. It's in C, and it's at least as hard as
everything else in the class. So we're starting to see a confluence,
between our strategic plan, amassing evidence for the intractability of tsp
by, arguing it's as hard as a bunch of other stuff, and, the mathematical
formalism. Right? This notion of completeness gives
us a language to say that a problem is as least as hard as a bunch of other stuff.
So, how should we define all this other stuff? That is what is a suitable choice
for the class c? Well, we'd like to present the strongest evidence, the most
compelling case possible, of the traveling salesmen problem intractable,
so that says we should strive for the biggest set c we can find.
The more stuff This problem is as hard as the greater the evidence of its
contractability. So, we want to prove it complete for a
really big set c. Well, why not be ambitious and reach for
the stars? Why don't we just show that the travelling salesman problem is the
hardest problem in existence. Its C complete, even if we take the set C
to be all computational problems. Well, this is a good starting point, but
it turns out this is too ambitious. We're not going to be able to prove this
fact. There are, indeed, computational problems
out there, that are certainly, strictly harder, strictly more difficult to solve,
than the traveling salesman problem. One I hope you've heard of is the halting
problem. So in the halting problem, its very
simple. You're given as input some code, say a
program written in C, and you're given an input, and the responsibility of the
algorithm is to decide whether or not, the provided program will halt,
eventually, when you run it with the provided.
Input. Perhaps the obvious approach to the
halting problem is to just simulate the provided program, in an interpreter, in
effect, on the supplied input. But here's the problem.
Suppose you've been simulating the provided program on the provided input,
and you've been running for say ten hours.
Maybe you suspect that things in an info, an infinite loop is never going to halt,
but how do you know? Maybe if you ran it for one more hour, it would halt.
What if you've been running it for 10 years?
Maybe now you're pretty sure it's in an infinite loop and never going to halt,
but how do you know? Maybe it's going to halt tomorrow.
Problem of not knowing when you're done, is an issue not just with the naive
simulation approach to the problem, but with any possible approach to this
computational problem. Indeed, Turing proved, in his landmark
1936 paper, that there is no algorithm, however slow Guaranteed to always
correctly solve the halting problem.So this is one of those theorems which is
simultaneously, at least in my opinion, very deep but also the proof is just like
4 lines. You prove it by contraction, you assume
that an algorithm for the halting problem does exist and then using the code for
that program you construct. A program that, on the one hand, can't
halt, and on the other hand, can't not halt, obviously a contradiction.
So the purported algorithm for solving the halting problem can exist.
So, and this is the kind of argument I find just Totally baffling.
I like to recall Von Norman's quote that, there's some things in mathematics that
you don't ever understand, you just get used to.
And this kind of diagonalization argument inspired by Kant, was originally,
original argument, that there's an uncountable number of real numbers, I
think fall squarely in that category. Anyways the point is that the traveling
salesman problem no longer looks quite that bad.
And we now realize that our original thought to prove that the TSP problem is
at least as hard as every other problem is a little misguided, is a little too
ambitious. So, it's certainly not at least as hard
as the halting problem. The halting problem is what is called
undecidable. There's no algorithm for it whatsoever.
Whatever time. Rather than I give you.
Where as the TSP problem by contrast, if I give you big enough time bound roughly
n factorial for n vertices, you can solve the problem namely using our favorite
punching bag Brute Force search. You can just try every one of the finite
possibilities and pick the best one. But the high level idea at the, top of
this slide, that is proving the travelling salesman problem complete, for
a big class of problems is, still a good one.
We just have to refine our understanding of the suitable choice of the class, c.
In particular By virtue of being solvable by brute force search, there are certain
problems that we cannot prove that TSP is at least as hard as.
But maybe we can prove that amongst all problems which can be solved, using brute
force search, amongst such problems, TSP is the hardest one.
Now to execute this idea we'll of course have to define what it means from a
problem to be brute force solvable. That would motivate the complexity class
NP, the subject of the next video.