Video 0-1: Hard problems, theory loopholes, outline of the module

0:04 In unit one, I'll want to I'll I'll give you a brief outline of what the module will cover and I'll try to motivate a bit why we uh why we embark on this journey together.

0:14 Um and uh it it will resolve around the question of how to solve hard computational problems. And there's a bit of a a problem there because they're hard because they're not easy to solve. So how are we supposed to solve them anyways?

0:31 uh if if you've done a TCS module in in undergrad theoretical computer science um you may have encountered the story behind this cartoon which is taken from uh I think the most cited computer science book full stop which is funny that it's a theory book maybe this is no longer true and some deep learning stuff is more more gathered more citations now uh it had some time to acquire those citations. Um, does anyone know the book by name? Have you looked into it? Yeah. Has anyone looked into it? Is um same as same as Don Canu's uh art of computer programming? It's a book famous to be uh to be known and bought but never looked into. Um it's a good book though. It's actually quite accessible and the writing is is is very well done. um which hopefully is why it got all those citations. Uh the story in there goes you're uh you're tasked to solve some computational problem. You're employed in industry and your boss tells you solve this problem and now and and you try you try to find an efficient algorithm that gets the job done but you kind of fail and then that's a bad situation to be in. You would have to walk up to your boss and tell I can't do it. I guess I'm too stupid. Like, okay, that's it. Um, a better option is to prove that the problem is NP hard, in which case you can point to this long queue of famous and and and clever people that tried to solve the same problem and also failed. So, at least your boss is not going to say, I'm going to hire someone else instead. Right? Uh, so there's an is an indication that a problem is hard.

2:23 That's what NP hardness is all about. It's a formal proof that it's as at least as hard as a lot of other problems that a lot of people have tried to solve and all failed in a specific sense. Now, that doesn't really solve your problem, right? It solves the problem of not being sacked. It doesn't solve the computational problem. So the the quote from the book is um at the beginning they tell the story with this with this guy in the cartoon and then many chapters later they come back to this story and say this is uh the bander snatch problem that's this fictitional computational problem that was this that the story was about it didn't just go away by uh proving it nplete it's still there and it's still not solved so what are you going to And that's the the starting point for this module really. Um whenever you have this is a NP hardness is an impossibility result or a lower bound.

3:27 It tells you that certain things are supposedly not possible. Now as always with complexity theory there's this fat asterisk to it that saying that we don't know whether it's not possible. We just can't seem to find a solution. And unless P equals NP there is none blah blah blah all that kind of um standard complexity theoretic assumption made um we can't solve the problem. So but it's it's an impossibility result and it's a very specific one. It tells you that this specific problem cannot be solved in the worst case exactly by a deterministic machine and so on. It's very specific and each of these components you can attack and check if there's a loophole around this hardness result about the impossibility result to get something useful. And we'll go through a couple of more or less successful loopholes on uh a lot of different uh example problems and see what we can do or also what we cannot do still. And here are the the typical loopholes listed.

4:37 Um uh I'll go through them in a bit slower pace in the next slides. Uh we'll cover the first four and not the last one.

4:49 Um that's a bit of a a personal choice. There's nothing wrong with quantum computers or quantum algorithms. It's interesting theory. Um we haven't seen a quantum computer that can do anything really useful. So it's it's definitely still a theory at best. And it's not clear how much they help here. Whereas the other examples, all of them have applications where they've proven to be useful beyond uh the general theory of of throwing up your hands can't be done. So, uh what are the loopholes? Um for each of those, uh it's essentially some some aspect of the impossibility result that we can try to attack. and uh we'll see um what we can do to work around those. So if if these are exploited, what can we do algorithmically? Can we solve the problems if that thing is avoided? Sometimes that's still not possible and there's refinements of NP hardart disuctions that show similar impossibility results including the loophole. Now even if you take that into account, the problem is still not easy to solve.

6:05 Um and that gives us examples uh where the loophole either works or not. And uh it's always good to see the the two sides of the line. Now for this for this module, we'll focus on I called it eternal truths, the things that won't won't age that quickly. Uh in particular, um rigorously provable results as opposed to um specific engineering ideas.

6:34 uh there's a bit of attention there always. So it's it's certainly more on algorithm theory than on on engineering and both is both is valuable and interesting but for this module there's a clear focus on the theoretical part um with the benefit that the things that we do prove they're going to be true forever. Right? this uh very good reasons why the models that we'll cover uh later in tomorrow um are really going to stand the test of time and not much is going to move there. Um and so that's that's eternal truth knowledge. Uh what it requires is a foundation in in math and TCS as I said because we'll use the tools of rigorous proofs. Um, also at times I'm picking example problems that illustrate a point pedagogically well, but are not maybe the most exciting application. That's always a trade-off, too. And I'm I'm striving for for including a bit of both.

7:40 Uh but the pedagogical examples often come first because they illustrate the technique and allow you to acquire the skill as opposed to learning a specific portfolio of a known solution. So a brief um outline of the loopholes that will each be a larger chapter of themselves later in the module. So chapter zero if you want or part zero will be recap on the classic NP hardness uh theory via the mini seminar and wire lectures uh today tomorrow. The first loophole that we'll look at is is large integers. Uh many problems talk about inputs that have numbers as part of them. And um sometimes problems are only hard if those numbers are allowed to be really big.

8:35 uh and more more formally a problem is encoded in binary at the end of the day in a computer and even on the formal models that we'll consider um essentially the same thing. So numbers are encoded and there's a difference between the length of an encoding of a number and its value. The value can be exponential in the size of the encoding. Right? If I if I write down a million, it only takes six or seven um digits. But it's a million, right? It's a big number and you can ramp this up more. So the algorithmic idea there is to design algorithms that exploit the fact that you have small numbers only. And sometimes that's good enough. Uh on the other hand, there's also problems where you can show even if all numbers are small, they're still hard. That's loophole one.

9:33 Uh loophole two is a generalization of this idea. Um I called it contrived worst cases which means the impossibility result says the problem in general cannot be solved efficiently unless P equals NP etc etc. Uh but that seems to be true for really constructed uh extreme cases that are unlikely to be relevant. And so um that's the idea of fixed parameter algorithms where on top of the input size n you decide on another thing that quantifies how difficult the input is and that's called a parameter and you analyze those together. Uh it's a very broad theory very effective in in many applications u but also not always applicable. So sometimes you can identify for a problem with a specific parameter that even if that parameter is small the problem is still hard in a that's the intuition. Okay. So that's that's the generalization. Before we had just large integers now we have some large property of the input and you get to decide what that property looks like. Uh the third third loophole is that the classical theory asks for exact solutions only. This only makes sense for an optimization problem. Say uh the traveling salesperson problem. You're trying to find the shortest round trip.

11:07 And um the the hardness often comes from asking for the precisely shortest round trip. And in practice, you're often fine with being it's 1% slower would hardly be measurable. Um, that's where this this part gets at. If you're only interested in approximate solutions, sometimes you can do better, sometimes you cannot. And the line between those is important to know. Uh, the last that we'll that we will look at is the idea of randomization. Uh, you've seen this in in other cases. It also in efficient algorithms makes uh um sometimes life easier to use randomization. Uh but the idea here is that it seems that algorithms fail to solve a problem efficiently sometimes just because they run into unlucky cases and uh you really need again a contrived input to run into exactly those. Whereas if you uh throw in a little bit of randomness and unpredictability in the algorithm, the hardness seems to go away. Uh this will be this will be a case where um there's a widely believed outcome. I don't want to spoiler now. Uh we'll come to that. Uh so the idea is to use randomness in algorithms and um see what you can prove about that not being helpful.

12:47 That's the four loopholes that we'll spend time on. Um the first one will be quick. The other three will be roughly a third of of the rest of the time. Uh the goal overall is to enhance the ideas you can bring to bear on an algorithmic problem that go beyond the NP hard or polomial uh distinction and also teach you a bit about how to prove that certain things are not applicable by proving impossibility results of various forms.

13:24 uh as I said the for the focus is on on rigorous methods we'll leave outside how to bring those into practice which is essentially a topic of its own uh and here's the rough outline planned um that's where we are that's uh what we'll spend this week on and then uh after the mini seminar we'll start with loophole one loophole two loophole three and loophole four. Uh as a rough indication of the time that we'll spend on uh if you look at this, it will not work out that they can each take a week. We don't have enough weeks if we take out the mini seminar. So they'll have to be a bit shorter. Uh but that's that's roughly the plan.