Video 3-1: Pseudopolynomial algorithms

0:05 Let us recap where we are. We've now covered again classic complexity theory, which is pretty much about bad news. We've covered these four pages of different interesting problems that model all sorts of um abstracted as versions of of real-life problems, and they're all NP-complete. So, what do we do next? And the first of these loopholes that I promised we'll look at uh is essentially using um then pseudo-polynomial time algorithms, which is a term you if you've not heard of doesn't help that much. Um it looks at a specific property of of these problems that they sometimes have, which is namely being defined in terms of numbers. And if these numbers aren't too big, sometimes uh the problem is not that bad to solve. Now, we'll see an example of that. And also the limits, um let's start a bit with uh making a bit more formal, a bit more clear what we mean when we talk about this um integer-based problems.

1:14 Um I call these integer input problems, where this this language that we care about is again you know, there's encodings for all valid valid problems, and then there's the yes instances. We're back to the threshold worlds, where we just decide a yes or a no. And if this input uh semantically means there is a sequence of integers behind it or involved, then let's call this an integer input problem. This is a bit of an informal definition, because it really is a semantic distinction. My point is here rather to make sure that we we uh define the scope of what's to come. For these problems, let's use this uh notation max int to just decode mean the modulus of the largest integer that occurs in this encoding. I think here if there's negative numbers is really the the absolute value that we care about.

2:20 Uh we assume that these are encoded in binary. That sounds very harmless and un- inconsequential. The point is just to forbid you from doing stupid encodings. So, it's not so important whether they're binary or decimal or so. This is all fine. Uh we might as well assume binary, but they shouldn't be blown up just to be uh taking up a lot of space. Uh we've seen many examples of integer input problems. Uh traveling salesman, traveling sales person, I guess. Um has the distances as input. Uh if for the decision version in all of these cases also the thresholds. Uh subset sum was this problem. Here is some numbers, can you make exactly this value T that I care about? Uh bin packing. Can I Can you partition the elements into not too large uh sums? Integer linear programming obviously is talking all about integers and the knapsack problem, which is the one I didn't properly explain.

3:25 Um so, maybe it's worth doing that now. Um No, I'll postpone it for tit for tat. Let's first of all discuss about the definition. Um just to check if if you're you're following in the thinking. This max int again is the absolute value of the largest integer that we encode. And if I have in total, say N bits in my encoding, how large can this max n be?

4:58 Is a bit informal. But I think the the only key part is um I mean, I insist that the numbers are in binary. With some sensible encoding.

5:36 I'll show some answers, you can still uh think about. Uh And this is three different answers. Four? What's the fourth? Unbounded. I guess I'm I'm assuming that you use an encoding that can represent every possible integer somehow. Um and is that kind of a worst case notion? Maybe maybe you thought too much about this. >> [laughter] >> Uh so what I what I had in mind is like of course upper bounds and if it the the real answer is kind of this one. I'll tell you a bit in a sec why. And then anything that's lower is of course also correct. Right? It's just um included in the previous one.

6:34 Uh why do I think that this is the right answer? Uh this is rather close and for binary kind of um the most extreme you can get. Of course this is uh I'm I'm slightly changing my mind because I really insisted on binary here.

6:58 The the worst case I can get is if the whole input is just one big number. And then I have a hard time imagining getting more than two to the end. The difference between these two is this is a arbitrary exponent exponential base. So if you use more symbols than binary, you might as well get 10 to the end or so. That's what I originally had in mind there. Now if with the previous slide restricting numbers to be encoded in binary, I think uh this is this is more more correct. And it's an upper bound because if you use more than one number, then you have to spare the bits spread the bits among all the numbers so they all tend to get a bit smaller. But you can make an exponential smaller by quite a a before it becomes no longer exponential, even though the base may be may be different. Okay. So, long story short, um long story short, in principle, it could be exponential.

7:59 It cannot be worse than that. That's some comfort. Now, what is this um pseudo polynomial thing that also popped up on the title slide? We call an algorithm for such a problem pseudo polynomial if its running time is bounded by a polynomial, but now not just the usual thing would have been just P of length of X, right? That's standard polynomial. Now, I'm allowing also this max int as a parameter in the polynomial. So, even a power uh a a an algorithm that takes as running time the largest integer to the 10th power would still count as pseudo polynomial. Knowing that max int might be exponential, that's a bit of a problem in general. Right? That's why it's only pseudo polynomial.

8:51 Okay. Um don't mix this up with quasi polynomial. By the way, I think these these terms aren't aren't great, but sadly, they're stuck we're stuck with them, I think. It's a bit pseudo polynomial has this max int flavor, and maybe it should be called max int polynomial or something different, but uh quasi polynomial is something entirely different. It's just a growth of functions, and the definition is this. It's two to the poly log. Which uh one log here would just be n. Log squared would be exponential.

9:29 Um would be polynomial. But uh with a higher power, it's it's not yet exponential. it's far away from exponential, but it's also no longer properly polynomial. Something like n to the log n. So so sorry, what I said was wrong. Um with c equals 2 is already n to the log n. That's already not polynomial. So that's We will not use this term ever again in this lecture. It was well worth spending a minute on it. Uh just so that you don't confuse anything with it. Now with this definition, if max int is small, if that is a polynomial indeed, then I'm inserting a polynomial in another polynomial, that gives me a third polynomial. So um that immediately means for for these problems where max int is small, uh um I get a a polynomial time algorithm overall. And uh I have a a proper theorem proving that, but um I think this was just a an excuse to introduce one more notation for this.

10:48 Um how should we deal with this? We have defined a a second parameter now for a problem, apart from its input size, it also has this value of the largest integer.

11:06 And turns out it's convenient to say I had to talk about the the sub-instance of these problems where this max int is not too large, that's from this note rather obvious. So formally, if you have some some increasing function and uh our decision problem, then we can define the h restriction of that problem, which is uh where all the instances are um having max int less than H as as a function of the instance. So, the max end of a certain instance is at most this function H evaluated at the length of that encoding. Okay?

11:50 And here's the the statement that I think doesn't need much of a proof, maybe. Um if you have an integer input problem and a pseudo polynomial algorithm for this problem, then the running time that that guarantees is indeed a polytime algorithm for the restricted problem. So, just inserting the definitions, well, let's maybe do it. A is a pseudo polynomial algorithm, so it has this running time uh big O of P, a polynomial in the size of the encoding, length of X, and this max end.

12:33 Now, let's write N for the size of the encoding. And if I have any instance of this restricted problem, this slight slightly awkward notation, um the hope is just that this is um self-explanatory.

12:57 If if you have any such such instance, then max end, of course, is at most this H. Inserting the definition of that one. And if um H is a polynomial, that means this thing is somehow N to the C for some constant.

13:23 For some constant C. And now I'm inserting this here and the argument from before. Right, it's the polynomial of some polynomial evaluated at a polynomial or inserting a polynomial in a polynomial gives you some other polynomial.

13:49 And so that's the running time of our algorithm A now bounded by a polynomial so it is a poly time algorithm but only on these instances that have small maximal integer. Okay.

14:09 Uh this immediately means for our optimization problems um that then this uh restricted version is also in PO by the same or by definition in PO essentially means that you can find a a solution in that time. So if you define a pseudo polynomial algorithm for an optimization problem, one where it computes the instance in pseudo polynomial time uh then you immediately get with the same proof this result.