Well, I want to tell you about one of my favorite algorithmic fun facts. Uh, it's it's it's it's kind of a party trick that uh perhap perhaps you'll enjoy. I don't know your sense of humor, but perhaps you'll find it as funny as I found it when I first learned it. So, I want to talk about shortest pauses in a graph. Are you familiar with how you find the shortest path in a graph at all? Uh, I know there's some different algorithms. We've already been to S, so we ignore it. We can go to Dyster's algorithm and stuff. Yeah. Okay. So, let's talk about a very simple shortest path in a graph problem. We're going to have two paths. So we're going to have like imagine I have a you know a start point and an end point and we're in a cartisian plane right? So I'm going to I'm going to describe everything by its x and y coordinates. You know maybe this one's at like you know 0 comma 8. Maybe this one's at a you know 12 comma 0. And we're just going to draw two options for how you get from one to the other and and connect them. Rightump plump plump blump blump blump. So the shortest path is kind of obviously going to be either this or this, right? Because it it couldn't possibly be anything else, right? So question, how hard an algorithm problem is it to find the shortest path in this kind of graph where it's on a cartisian plane and there are exactly two possible paths? Uh in in what? Measure it in what way? How do you mean? Let's let's talk um let's talk bigger. With bigger, we only care about the highest order term. Is this NP? Is it NP hard? Is it uh does it take exponential time? Like is it n squ time? Like what do you reckon? I I don't think it's going to take long at all because it's you've just got to traverse down both the paths and count, right? Yeah. So you might have heard of like SAT, right? Like the the SAT problem, famously hard problem. So SAT is this um satisfiability problem where we write down a bunch of constraints. Like it's it's basically a generalized form of like Sudoku where you're trying to fill in various variables into a grid and you've got some rules about what you can um about like what the values properties the values have to have. like you can't have more than one in a column. So SAT is like a a generalized version of this kind of problem where you have constraints and you have to choose values to match the constraints. So it sounds like you think that probably this problem is easier uh than SAT. Yes. Well, that is as far as we know incorrect. Okay. Uh this problem no one actually knows how hard it is. Uh but no one has any proof that it is easier than SAT. Uh and and currently currently it's unknown. Is that because as a computer you don't know there's two paths? Is it just cuz we're looking for? No, we tell it we tell it there's two paths. Okay. Uh so so so here's why it is. So how how do I calculate the length of one of these paths? So so the algorithm here is obviously going to be well you either want to do path one or path two. Right? So what we got to do is compute the length of path one compute the length of path two and then figure out which one's smaller and then pick that one. Right. So it's just going to come down to the question of determining which of two paths in cartisian space is shorter. Right. Okay. Yeah. So that that might So how would you do that? I I'm not entirely sure. You got to find the vector of each jump and then go from there. Is it like that? Well, yeah. I mean, suppose I want to go from like uh suppose I want to go from 4, 8 to, you know, 6a 5. How do I how do I calculate the length of that that step in the path? There's some kind of like triangulation thing with like paragraph and stuff, but I can't remember it off the top of my head. That's right. So, you know, Pythagoras's theorem says the length of the hypotenuse is the square root of the sum of the squares of the two lengths. So in this case, it's going to be the square root of the vertical distance I traveled, which is three. Um, and the square root of the horizontal distance I traveled, which is two. Right? When I calculate the length of this path here, it's going to be a sum of a bunch of square roots. And the other path is also going to be the sum of a bunch of square roots. And so the question we have is how hard is it given a list of square roots and another list of square roots to determine which of them has a bigger sum? And it sounds like you think it's not going to be that hard. Well, you got to just add them all up, right? You've got to just Yeah. Okay. So, so when you say Yeah. So, you're like intuitively the thing you want to do is you just want to add them all up. Yeah. And then see which one's bigger. Yeah. So, the thing is that might actually be extremely hard. So, here's why. When you say add them all up, uh square roots famously, uh might lead to irrational numbers which are just, you know, have extremely long expansions. So, it sounds like the thing you want to do basically is you write down your square roots uh and then you add them all up. Uh, and to do this, you have to have some idea of what precision you wanted to compute the square roots to. So, the basic issue here is, you know, pick your favorite precision. Maybe you're like, I think we're only going to need four decimal places here. So, you compute this square root to four decimal places and this square root to four decimal places and this square root to four decimal places and these ones as well. And you add them all up. Now, suppose you got the same thing. What are you going to do? Probably uh the lengths are actually different. But it's the precision that's the problem. Yeah. So, so you're going to be like, "Oh, no. I guess we have to do it again, but to higher precision." And so the basic issue is for all we know, if I if a square root is just, you know, a long sequence of arbitrary numbers, you don't know what precision you have to compute it to ahead of time. And so what you're going to have to do basically is just keep computing in greater and greater precision until the digits vary, right? Like it it only takes you, you know, some amount of time to compute the nth digit of a square root. And so you can just like it's not very hard to calculate two n digits of precision. But we if we actually want to make sure that we have an algorithm that works in every case, we have to make sure that there are no sums of square roots that match for an ungodly amount of time before eventually disagreeing. Right. Yeah. And knowing whether that's the case would require knowing a complicated math fact about sums of square roots, right? Like is it ever the case that I can write a short uh pair of sums of square roots such that they agree until the 20th trillionth digit or whatever the you know like a gazillion you know Google plexi whatever many digits of agreement and then at the end they like differ this one has a four and this one has a five so I guess this path was shorter and no one knows uh whether it is possible to write short sums of square roots that differ after you know a squillion places and so as far as anyone knows this problem is uh very hard. So, but that's like general in general. It's in general, right? Yeah. In every case anyone's ever tried, it's very easy. But when you're doing algorithmic analysis, you know, you really want to know the worst cases. And the reason why I find this so hilarious is that finding shortest pods in a graph is classically considered a very easy problem, right? Like Dyster's algorithm is like n login or whatever. Like no problem. People do it in practice all the time. But I just think it's pretty funny that if you actually want to do the algorithmic analysis for this innocent looking problem, it it it actually turns out to be uh basically infeasible to analyze. Uh so this is just my this is just my favorite fun fact of a thing which seems like it should be really easy but is actually really rough. What Dyster does is basically similar to a sort of brute force flood search through this space, but does it in a kind of in the order that makes most sense based on how fast these roads are. So it'll check the quickest roads first. So to do dyes, we need a few things. First of all,