Video 1: Motivation

0:03 After you've experienced a bit what vertex cover looks like, uh let's continue with the overview of the module. And maybe you have a bit of um a concrete problem now to tie uh the more abstract concepts that are coming to.

0:26 This is um the overall theme, if we have problems that are hard in a specific sense, and in particular NP-hard is the usual one that we have in mind, then we may still want to solve them. Uh I don't know how many people know the actual book here that's on the cover. Uh if you're looking for a a reduction that proves that some problem is NP-hard, this book is often still a go-to one. Even though it's it's rather old, it has a lot of classic problems in there that often are enough to show hardness for new problems. Um I'll revisit the theory of NP-hardness in the next unit. This is something that I would expect you've seen before, but we'll briefly run through that again uh just in case and to set the notation et cetera um the same for everyone. The the cos path or the the kind of theme of NP-completeness and NP-hardness is that that you're this guy who is asked by your boss in a company to solve a certain problem for a coding application.

1:34 And um somehow it doesn't work. You're not You're not getting a solution. And one option is you're not smart enough, but the other option is it is genuinely an almost impossible task. And NP-hardness lets you point to all all these other people all these other problems have never found a solution, so maybe I'm excused not to find one for my problem, as well. And this is underpinned with a specific piece of theory, NP-hardness reduction or polynomial-time reductions.

2:09 Now, another quote from the same book. This is the the opening part is ah all a bit negative, there's some of these problems that just seem collectively hard and we haven't found a crack to to solve them faster. But then the story goes on. Ah, you had just neatly sidestep potential charges of incompetence by proving that the Bandersnatch problem, some hypothetical problem that you're solving, is NP-complete. However, if the Bandersnatch problem had refused to vanish vanish at the sound of these mighty words, and you're still faced with the task of finding some usable algorithm for dealing with it. So, how do we do that? If a problem is not generally solvable, ah, the theme for this for this lecture is let's look for loopholes in this impossibility result. The fact that a problem is NP-complete or NP-hard has a very specific precise meaning. And if you look at the precise meaning, there's several places where you can wiggle a bit and then maybe this hardness falls ah together then dies away, goes away.

3:16 Or maybe not. Sometimes it does, sometimes it doesn't, and it's problem-specific. Ah, here's a few examples. Um Maybe the problem is only hard if it's a number problem, it deals with numbers, and the numbers are large. You can have many numbers, if they're all small, it's fine, but if they're large, then it's problematic. Or maybe there's some notion of what makes a problem hard, and we'll see [snorts] many examples. This is a bit abstract, but maybe you can think about um What's a What's maybe a good example that is that doesn't need much context? Uh maybe everyone knows the traveling salesman problem.

4:03 And um maybe there are certain types of graphs make the problem easier. Say if if uh uh it's defined in the complete That's a not so good example, traveling salesman. I think vertex cover is better, the one we've seen in the game. You've certainly seen some examples of graphs that are easier. For example, if the graph is one long path, the problem becomes completely trivial. Maybe there's a way to measure the path pathiness of a graph and stick a number to that. And then you can study whether the problem is is easy if that parameter is small. Or maybe we give up on solving the problem exactly optimally and are happy with some approximately optimal solution. Maybe the problem is only hard if you insist to have a predictable algorithm, and if you allow the algorithm to throw in random choices, randomized algorithms, it suddenly becomes much easier to solve. Um slightly um related maybe um the slightly different tone is maybe the problem is hard only for certain really contrived inputs, and if you modify them a tiny little bit, then the hardness goes away.

5:19 Uh we'll not talk about quantum computers. In theory, that's another option. In practice, it seems we're many orders of magnitude away from them being useful for most of these problems.

5:40 Now, for each of these potential loopholes, I said some problems allow us something with this under this angle and some problems not. So, for each of them we'd like to have algorithmic techniques that if this works, we can get a faster algorithm to solve our problem. But, we'll also want to complement them with some some guarantees of the opposite kind proving that a certain thing is not possible. That's what NP-hardness originally was for. Now, if we remove some of the defining parts of NP-hardness, it's no longer an obstacle in itself. Um but uh you can refine this kind of reduction um idea from NP-hardness and can rule out that certain solutions work for certain problems. That's uh what we'll also look at. Um you can also take um the same questions and approach them from a practical perspective only that you say, "Ah, there's maybe for my vertex cover problem, my streets always look a bit like this and I only have this benchmark data set I care about. Let's just build some heuristic that works for these and and leave it with that."

6:52 I find that not satisfying. I want something with a provable guarantee of a certain kind. Guarantee can mean many things in this case. And so, ultimately it's still about um provably correct algorithms. Where correct maybe now has a slightly more refined meaning. And to do that, we need some foundations in in math and in TCS. Uh that's what the the focus of the module is. Push with theory techniques against NP-hard problems. And show what does or what doesn't work.

7:41 Now, for each of the loopholes that we'll look at, there's um certain specific things you can you can try. Uh For the large integer case, we'll talk about pseudo polynomial algorithms. Um you'll see what this what this is in the upcoming units. So, here I'll basically just throw in a few buzzwords that maybe many of you don't know yet. Uh this is rather to tie things together at the end. Uh it's not expected to make sense at this point. And you can show that a problem is strongly NP-hard, then it can't have such a pseudo polynomial algorithm. Uh loophole two was this notion of a parameter that the input is somehow not just has a size, but has a parameter K that somehow tells you how easy or hard a certain instance is. Um and the design technique there is called fixed parameter algorithms. Basically, it doesn't tell you how to design the algorithm. It just tells you that the running time is now measured differently.

8:41 You're allowed to uh grow very quickly in terms of your parameter, even super exponentially, anything is allowed, but the rest of the time must be polynomial in the same same efficiency notion as for NP prob- P problems.

9:03 Sometimes you also have a bit more. Sometimes you can specifically give uh design um design strategies for building such algorithms. I'll look at both a bit. And as before, there's a complementary notion of hardness that proves for a certain problem in a certain parameter, you're not likely to find such an algorithm.

9:30 Then uh next one is um randomized algorithms, where somehow the loophole is uh maybe uh just fixing an algorithm up front makes it easy to find bad examples. And once you allow some randomness, um you don't have these unlucky decisions anymore. Um there obviously the algorithmic approach is to introduce randomness, and it's often even okay to say I'm allow I allow the result to be wrong with this probability.

9:59 Well, we'll talk about these these two notions in detail. Uh here the impossibility results are a bit more interesting. Uh this is one of the big open problems in theoretical computer science that there's randomized complexity classes, the equivalent of of the class P. Um and it seems that these are the same as P, so that randomization doesn't formally make the the set solvable problems bigger. But it's a big open problem, and nobody knows for sure. Uh we'll talk a little bit about that. It's also fascinating area. And lastly, um you can give up optimal solutions if the problem is an optimization problem, like in vertex cover. Maybe I'm okay with not with you not finding the smallest number of lamps, but at least uh close to optimal. Uh that's what approximation algorithms mean. Uh sometimes you can even give these uh approximation schemes where uh you can give me an approximation of any guarantee. Now, I'll first fix how close I want you to be to optimum, and then uh you take more time the closer to optimum you need to be.

11:15 That's behind these uh PTAS FPTAS. Um but sometimes also this is not possible, and you can show via reductions when this is not possible. That's roughly the overview. So, in each case you see is is some algorithmic techniques, and some lower bounding techniques of some sort. It's always some reduction from other problems. Uh so the module is a bit say 2/3 algorithms and 1/3 complexity theory.

11:51 Uh the preliminary plan uh looks like this. So, these are the different units that you also find on the website. Um and how they address these loopholes roughly. Uh the goal is to roughly spend a week on each. But again, uh this is this is going to be true on average, not for each individual unit.