0:43

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.

Â