Video 1-5: Pseudopolynomial Turnpike algorithm

0:04 after this somewhat negative result in a sense that we have an algorithm that seems to work okay but is exponential in the worst case and we don't even really know what the complexity status of the problem is in in a complexity theoretic sense is it P is it NP somewhere in between or even worse who knows uh there's at least one other positive thing that we can say um and that's a kind of other other nice detour. Sometimes if these combinatorial problems seem hard to make progress, you can pull tricks from other areas of mathematics and uh in this case algebra to help you out. Uh partly to get a different perspective on the problem and partly to just ride the wave of existing results that people have worked out for these So um apart from what I've shown you this uh exponential uh backtracking algorithm and what's coming in a sec there's not so much known that works for this. Um maybe that's an area where uh one can still make some some progress.

1:18 Now let me briefly describe the idea. First of all uh here's a concrete example to work on this. That's again our uh sum some some uh quote unquote random input and it's difference subset multi set. Um and let's do something nuts. Let's just write this as a power series or a polomial in the following way. we take the powers corresponding to our uh prefix sums and we'll just form a polomial of of that by taking taking the respective powers and if you had several occurrences of the same number well in s it won't happen by definition uh in in D it can happen then you get just a a factor in front of this now if you uh just take this definition And for some reason decide you multiply this polomial with what you get if you uh insert uh set to the minus one then you get a product of of two well rational functions or generalized polomials polomials uh is this the name that people give if the exponent can be negative. Um here we just treat them as algebraic objects. So it's it's kind of only in a in a a in a formal sense as as these sums in some uh ring over over uh structures. There's no it's not treated as a function in set.

2:56 Now if you multiply this out what you see is uh you get one contribution set to the 11 from set to the 11 and one. And that's one of the differences. it corresponds to taking 11 and subtracting zero. Uh and then maybe you get C to the 9 from also combining these two. But you can also get uh Z to the 8 by doing C to the 8 * 1 or by taking C to the 11 * C to the minus 3. And that's why there's a two and you see that you get two occurrences of the of the difference eight in the multis set. Now this is not so surprising um because the product of two polomials is exactly defined as taking every pair and summing up the exponents. But of course you noticed that I cheated. The product keeps going. uh I've only taken the ones in the first row where the exponent happens to be positive. Uh but you also get the mirror images. You get the same combination. If you take 1 / C to the 11 * 1, then you get the same but with the negative power.

4:16 And then there's the five at the end. This is essentially a Z to the 0ero. Right? there's uh five ways of getting getting a different zero which is exactly by combining like powers. So this this five just comes from the fact that I've started with five numbers. So far so good. This is just some I don't know uh uninspired translation to an algebraic structure. Uh of course I can write down what this product looks like. In general, I'm taking entries from the sets all pairs and then take their difference. So, of course, this has something to do with our difference multis set. Uh, as I said, it's it's not exactly how we defined it. It's taking both the positive and negative version of all differences and it happens to include also the zeros where you subtract the elements from themselves. But this is more of a cosmetic change. We can convert from one to the other without thinking.

5:19 So if you want you can write this as the sum of this this this good part that corresponds to our original uh difference multi set and it's a negated cousin and then just the size of the input. Okay, that's kind of cute. Uh what should that be good for? Well, the other piece of of knowledge that one may or may not have, but you can look it up or you can learn about it is uh there's algorithms to factor polomials.

5:51 I'll I'll show you an example in a sec. Um there's another little cheating here because this is not really a polomial, right? Uh if you if you multiply this out, there's these negative powers and maybe that gives you a bit of a a funny feeling. We'll come back to that. Uh this is kind of easy to uh circumvent. Um if you start, so maybe I should stress this more. This part down here, this we can compute just knowing the difference multi- set. Well, the first part I started up here knowing the set S, which is what we're trying to find in the turnpike problem. So we don't have that. But D the difference multi set that's our input for the problem. This we have. So this sum we can easily produce this the same and this well we can work out what the size of s is because uh the size of s um well the other way around is a bit nicer to write the size of d taken in the sense that you sum up the multiplicities that has to be um s choose 2 in our original version or here I guess it's just uh squared but our original d in the definition we make order pairs.

7:11 Um and so if you have d you know its length you can of course work out how many uh you will have here you have to solve this uh horrible quadratic equation.

7:28 So we can construct the uh expanded polomial the expanded power series easily from the input of the turnpike problem. What we cannot easily get is this this factorization into these two nice terms and also maybe our input is not um a valid turn difference multis set then there shouldn't be such a factorization but this is where the um the algebra and computational or computer algebra comes in. Uh there's algorithms that take a polomial over you have to specify the field that the coefficients are taken from. Um and the precise result uh with parentheses missing is that if you have a a polomial of degree D the largest power that occurs and coefficients that have a certain size represented as integer numbers with B bits. then you can factor this polomial over the integers meaning uh you're only allowing integer coefficients uh in in time that's polomial in d and b in particular for b that's exactly what we want because that's the input size if I write down a polomial I'll have to tell tell you the coefficients and I have to write them down in binary that's essentially the best way to do um and the degree well that depends Right? Uh I could write down the powers as binary numbers and then my input might be much much shorter in the binary representation as the degree. If the polomial is full if it has all powers between the degree and one then my input is just as large as the degree and then it doesn't make a a difference. But I could have a polomial of a a humongous power and then maybe just some smaller terms.

9:26 This I can encode in much smaller space than this degree is. So in in general the degree can be an exponential blow up from the input size. The encoding of the input of the polomial in bits that's why an algorithm with this running time despite there being a polomial so I'm just using poly as an abbreviation. There's some there's some input size and that's raised to a power of D and or B. Um, sorry, it's no there's a function that is a polomial and you insert D and B. So it can be a constant power of D and a constant power of B maybe multiplied together. That's about the worst it can get. So maybe a a sloppy way of writing this would be uh d * b to the constant power something like this. Uh that's allowed. So it looks like it's polomial polomial bound but it's not polomial in the input size and that's what we call pseudo polomial.

11:06 It is polomial but in the value of the numbers that we give as input but we can represent represent those numbers very succinctly namely with roughly log uh the size of the number bits and so if you apply the algorithm you can have give it a short input but the algorithm might take exponential time on this short input so it's not polomial time it is only polomial if you restrict all the numbers that occur in the input to be small. If the numbers have polomial value, then it's polomial overall. That's another way to put it. Which means if all the numbers are bounded in some polomial size. So uh in value it's a bit of a nitpicky thing that you distinguish between the value of a number and its encoding size but it becomes an important distinction in complexity theory. In particular, this algorithm um doesn't doesn't imply that uh we have a polomial time algorithm for our turnpike problem. But we have a pseudo polomial time algorithm which is at least not not useless.

12:35 Uh because if you think about what the degree of the polomial that we're trying to factor is, that's the largest occurring number here, which is the sum of all the weights in our protein. So in a way uh the weights are kind of fixed. These are fixed amino acids. There's not new new ones invented all the time. It does scale with the length of the protein which is a problem. But for small proteins you might be able to apply this algorithm uh because the numbers that are involved are small.

13:16 Now uh there's also a bit of cheating going on with the polomial. So And one hack to make it one is to multiply it by the largest negative power that occurs or in general I could maybe give that a name but let's let's let's leave it just here for the example. Uh it's just the largest entry in D. I think we've used little d for that in the algorithm. But uh since we also have degrees of polomials, it's maybe not a good choice. Um if I if I shift all the powers then it is a polomial and by and large you can apply the algorithm on that thing instead and uh patch it up in the end. Uh uh at this point let me maybe show uh what this can look like.

14:39 So, um, it's one of a kind of a side story. Uh, I knew how to do this in Mathematica, but I didn't want to use software you can't have access to. Uh, so chat assistants are pretty good at translating code. Uh so with a little bit of help from Gemini in this case I think um you can translate the Mathematica code to uh uh Python some Simpai code. Um so some of the code looks a bit strange because it's AI co-produced.

15:12 Okay, I'm I'm going to be open. Um so here I take um I take the solution as input to construct the polomial conveniently and if you remember this was the example we worked out on the pyramid. Okay um then okay I'm I'm first compute constructing the input for um our our real problem. This is in a way not what you would normally start with. you would start with the difference um the difference matrix or rather the the list of differences. Uh so there's a a shorter way to take all pairs right this the outer product uh and then you flatten the list that's not so important. So the differences is the input to the turnpike problem. Apart from this it's also the negative numbers included.

16:08 uh we take the largest of these um and then we build a polomial which is for all the uh numbers in the difference we take zed to the power of that thing but we add the largest to get a real polomial with non- negative powers of zed okay and then um to make well this is a list of terms to make it a polomial I have to sum them up so if you run this uh Okay, life execution. I've run it before and it worked. So it seems seems safe enough. Uh the large the longest time is the initialization, right? It's a small input. It's uh it's pretty quick. So that's the difference set. You see it has the negative and the positive numbers. But if you focus on these ones, that's the input that we worked on in the example before. Uh and here's the polomial that we generate for this example. It has the structure that I've shown you in in symbolic on the slides. So that's not surprising.

17:12 Uh now how do you factor a polomial? That's the interesting part. And so simp has a a polomial class poly. You have to define what the variable is. Um and a was just this uh symbolic representation. This is a instance of this poly class. I I think this import should be duplicated. Okay, it's not it's not needed by name before. Okay, it's an instance of this though. Um, okay, maybe not. Sorry, this is just the expression. You have to for the polomial you have to specify the domain of the coefficients. And this is a critical thing in general. If you do math by uh by hand, you don't think about this all that hard and just apply the right rules on the fly. uh for computer algebra you have to be very picky about uh what the objects are you're talking about and here you can specify this way that the coefficients should all be integers.

18:15 Uh and then you can just call this function for factoring. Now if you run this is also very fast even if you make the example a lot bigger. Uh what you see here is though that the result is a little less clean than we would like it to be. It did a two too good job. It found further factors of this polomial namely there's one with multiplicity two. So you have a z^ squ + 1 squared and then you have two pairs of uh of polomial factors. These correspond to the positive and negative parts. And I think it's it's not 100% obvious which ones to pick but there's a small number of these. So in in essence uh you see that they come in pairs just by uh the largest degrees and um three of so these are six six factors in total. You have to take three to make the positive part and three to make the negative part.

19:15 And if you pick the right ones so in this case we pick this one the first and we pick this one and the last one. If you multiply them again, that's what I did here, you get back our polomial with the actual input that we uh that we arrived at or that we started with. Okay.

19:39 Uh and if you um if you mess with the numbers, say we make this uh some numbers, so it's unlikely to work out. Uh let's just go to 19.

20:09 This might have actually worked. Cool. Uh or maybe not. There are large factors here. So, um even if you multiply this might not work out. Let's let's try a more extreme example where it's more obvious fun. Okay, I should have prepared an example where it fails more badly.

20:46 If you make this big enough and it's the only difference of that large, this can't be a difference multi- set. Okay, we see it takes a bit longer.

21:10 Okay. I'm uh I'm not good at coming up with negative examples. What you see if you put in some random numbers um that are not a difference multis set then you'll you might still get factors but they don't match up in pairs. There's no way to make them one the mirror image of the other one being all the exponents negated uh from the other.

21:35 Okay. I felt after doing just this abstract algebra I felt you deserve proof that this this can indeed be done is not even so hard to use. Uh the algorithms that are behind it are somewhat sophisticated. Um but it's also okay sometimes to use a black box and leave it as that as such if you uh know what the constraints are.