Video 3-1: Pseudopolynomial algorithms

0:06 In unit 3, we'll look at pseudo polomial algorithms. The first example of something where we can take an NP hard problem and still do something about it, at least for some problems. And uh this will be a relatively short unit. There's not a lot of deep theory in there, but uh it's a it's a cute observation and is a a good segue into the the next unit. So, we'll just we'll start with um a little bit of a definition just to uh to set the stage. Uh this is a lightweight and slightly vague definition. Um an integer input problem. uh it's just an uh sum some some problem can be an optimization problem or it can be a decision problem uh where part of the input the instance consists of numbers. Um so formally you could say it's it's some arbitrary string and then a sequence of integers. uh all that we really need here is that for a given input I can I can say what's the largest integer that occurs as part of this instance. So again um uh we've seen some examples before and if we pick uh tsp as the prime example max in would just be the largest distance that occurs uh in in your distance matrix.

1:52 Thanks. So simple simple definition. Um the point of this is just not all problems are integer input definition in input uh integer input problems. Sometimes the input is all about strings. Say this closest uh string problem where I'm giving a list of strings and okay there's how many uh differences do you allow. But if you say the optimization problem of that uh then the input would just be strings then there's no integer associated with that.

2:29 Now, as a warm up, let's uh let's think about how big or small this max in can really be because that will determine what how hard you have to work in the following.

3:49 Okay, I'll switch over. Um, yeah, just about fit all all the slide. Uh, I guess 11 people is mostly it. So, here's your votes. And, uh, you can you can select more than one answer. And because these are big old downs um many of them are true. Uh let's discuss this briefly. So uh all of these are possible as how big max in can be as a function. So the extreme case clearly is that my input is just a single big integer. Okay. uh then it could be uh still a tiny number if I somehow prepend it with lots of zeros or maybe it's not the only thing in the input. Uh it could be really small. What's the largest it can possibly get? I can use all the uh space I have for uh digits of a number. I could certainly write down 2 to the n one with n zeros something like that.

5:02 I can do slightly bigger because in general my input alphabet isn't restricted to binary and so I can effectively achieve so this is this constant in the exponent is just transforming the basis to a different constant this is uh essentially c to the n or any c or any constant uh c and by uh using a larger alphabet that I can achieve that is a bit cheating in the sense that uh we think of n as being the same independent what the alphabet is but the touring machines always force the the alphabet to be constant size. So in in a way it's uh it's okay but um you you can debate about this and maybe it's enough to do binary numbers especially because I put binary here on the slide so it's maybe a bit up there uh but clearly there's an upper bound you cannot go above that so also this max int cannot be arbitrarily bad okay it can for example not be doubly exponential and is certainly always bounded in terms of the input size. By the way, if you're wondering how to specify an integer without telling you up front how many digits it uses, there's a nice solution that some of you have seen in in efficient algorithms. Um, sufficees to say it's possible even if you just have binary alphabets. Of course, with more alphabets, it's easier. You just put a special symbol as end of number.

6:45 Okay, so still it could be exponential. That's the point. Which means if some algorithm has a running time that depends on max int, it might be an exponential time algorithm. Uh nevertheless, we'll do the following definition. Um we call an algorithm pseudo polomial if its running time is a polomial of uh the size um of the input n and this max integer. So in particular this means uh that the overall thing could be uh exponential. So pseudo polomial time does not mean polomial time. Right? That's quite clear. That's why it's only pseudo polomial. Now maybe this term is not great. And there's another term quasi polomial which means something entirely different. I just put it there so you're not confused. It will not pop up in this lecture but uh or in this in this module. Uh but um if you just vaguely remember it was something like polomial. Um the term is not super great. It's not quite polomial. But why do we call it pseudo polomial?

8:17 uh at least it has some form of polomiality if this max in is small right that's that's where the name comes from I suppose uh specifically um if we can bound max int by some polomial in the input size then the overall thing is also a polomial a different polomial that's just because if you um if you insert say Okay, max int of x is uh we use n as the length, right? Maybe this is less than n to the 10th, right?

9:04 uh and then maybe this p is I guess two variables n and m is less than n * m to the 5th then if you insert this uh 4 m n * n n to the 5th is a lot but it's not infinite. It's n to the 55 n to the^ 55 is not a running time that we would like for any practical algorithm but it's polomial. What I'm saying here is if you insert one polomial into another polomial as one of its variables it remains a polomial just of different degree.

10:08 So if max is bounded by a polomial a pseudopolomial time algorithm is actually polomial time. Okay. uh to grab this formula this another definition um we take a problem uh u and we take a bound on the maximal integers that are allowed and then we say value of this bound subscript u is a new problem but one where I'm only allowed to use inputs where the max in is small smaller than h okay so uh think of all TSP instances where the distances are at most 10 or a function of the input size at most square root n uh that's up up to you and then we can have this uh this little theorem. Um we have an immediate input problem and we have a pseudo polomial algorithm for this problem. Assume that exists. uh then indeed for every polomial h if we restrict this problem to only max int smaller than h there's a polomial time algorithm for this for this sub problem So this uh this a has a running time which is given by some polomial O of P of the input size and max int.

12:12 parenthesis. So if we're given some input in this restricted value u. Then for this instance max int is at most h of x, right? And this is a polomial. So this is order n to the c for some constant c depending on this polomial h. And so the running time of the overall algorithm is we just insert n. I'm using n again for the size of the input as always. And max int is this. So order n to the c and that's another polomial just as we discussed now for another constant d. So a runs in polomial time for all x in value h of u. Okay, that's uh that's all there is to prove here.

13:38 Uh so if this is a decision problem then the value restricted problem is in P. If it's an optimization problem the value restricted problem is in PO. Works both ways. Uh it doesn't matter what the algorithm does if it decides and just outputs yes no or if it actually finds a solution.