The most powerful (and useless) algorithm

Video Statistics and Information

Video
Captions Word Cloud
Reddit Comments
Captions
This is the continuation of our previous video  where we revealed that we found the asymptotically   optimal algorithm for factoring. You can check it  out if you haven't yet, but hopefully this will   make sense even without it. As many of you have  guessed by the date that we published our previous   video, it wasn't completely honest. The fact that  the video suggested that we solved one of the   biggest open problems in computer science may also  have been a clue. But you know what? Although the   video was heavily misleading, what we said there  was actually true! Remember, we said that we have   a concrete asymptotically optimal algorithm for  factoring composite numbers. Before explaining our   algorithm, we need to understand the following  pressing question - why aren't we famous?   After all, it's safe to say that even determining  whether there is a polynomial time algorithm for   factoring would be worth pretty much any price  a mathematician or a computer scientist could   dream of! And so, the only possibility, however  weird it may sound, is that although we know   the asymptotically optimal algorithm, we  don't know what its time complexity is!   Okay, but even if we can't compute  the time complexity of our algorithm,   why not just run it on real instances like the  one mentioned in the previous video? If we can   solve the factoring problem really fast,  we can break the famous RSA crypto system,   so who cares that we don't have a proof that the  algorithm is fast! Since we're not famous yet,   the only possible conclusion is  our algorithm must be very slow  in practice. Remember, in computer science,   we're using asymptotic complexity because it's  often hard to distinguish whether the complexity   of our algorithm is, let's say this, this, or  this function. So, to make our life simple,   we ignore the leading constant and the  lower order terms and just call all of   these functions O(n^2). And that's reasonable  most of the time but what if the complexity was   1 million times n^2? That's also O(n^2), but the  algorithm would be extremely slow in practice.   So, asymptotic complexity can sometimes be  deceptive. That normally doesn't happen,   but you'll soon see that our case is, well,  very exceptional. Constant factors in our   algorithm are so ridiculously massive that  it struggles to factor even the number four. So, with these two points in mind, let's now  have a look at what our algorithm actually does. You may have heard of the infinite monkey theorem  - it says that if you give a monkey a typewriter,   after enough time of mashing keys randomly, it'll  eventually manage to write the complete works of   Shakespeare. But you know what? With enough  time, the monkey will also write all kinds of   valid Python programs (and in the remaining cases  Perl programs). And now even though I don't know   if there is an efficient algorithm for factoring,  if there is one, the monkey will eventually manage   to type it out in Python, given enough time. And  this is exactly the idea behind our algorithm.   Instead of hiring monkeys, we're just going to  iterate over all strings in their lexicographical   order and try to interpret each one as a Python  program. We'll give the program the number we want   to factor, let's say 4, on standard input we'll  run the program and check if by chance it printed   the factorization of our number to standard  output. Of course, most of the time we'll simply   get a syntax error, but on the few occasions when  the program does finish, we'll check if it printed   two numbers whose product is 4. Needless to say,  this also usually doesn't happen, in which case   we just continue with the search. But there is  an issue with this approach - at some point,   we'll encounter a program with an infinite  loop like this one. And when that happens,   our search will just get stuck forever.  So, we'll have to be a little bit smarter. We'll maintain a list of simulated programs. At  the beginning, this list will be empty and we're   going to proceed in iterations. In iteration k,  we first add the k-th lexicographically smallest   program to this list and then simulate  one step of each program in the list.   In this animation, each gear represents simulating  one step of a program, where you can think of one   step as one CPU instruction - for example, adding  two numbers, assigning a variable, and so on.   After we're done with all the programs in  our list, we go to the next iteration - add   the next program and simulate one step  of each program in the list, and so on.   Of course, sometimes it'll happen that  the simulation of a program finishes   either because the program returned an  answer or, more likely, it just crashed.   Then, we check whether the output of the program  is two numbers whose product is equal to our input   number. If not, we just continue with the  simulation. But in the unlikely case that   the finished program actually returned the correct  solution, we print it to the output and terminate   the whole search procedure. Fortunately, this  final check can be done very quickly and notice   by the way that this is the only place where it  actually matters that our problem is factoring and   not something else. And that's the whole algorithm  - it was discovered by Leonid Levin and is known   as Universal search so let's use that name from  now on. Perhaps you can already see how it's   possible that we have no idea what the asymptotic  time complexity of this algorithm is and why it's   so slow that it struggles to factor the number 4.  But the only thing we promised was that Universal   search is asymptotically optimal. In other words,  we promised that whenever there is some factoring   algorithm with time complexity f(n), then  Universal search has time complexity O(f(n)).   For simplicity, I just explained the version  of universal search that has a bit of a weaker   property - whenever your factoring algorithm has  time complexity f(n), I can prove our Universal   search has time complexity O(f(n)^2). I'll now  explain this complexity and then I'm going to   tell you how to improve it to O(f(n)). So, let's  say you give me some program that needs f(n) time   to factor numbers with n digits. To have a  concrete example in mind, we can think of   the simple program that tries to divide the number  by 2, 3, 4, and so on until it succeeds. The most   important observation is that Universal search  will at some point start simulating your program.   For this program, it'll be the iteration  number - well roughly 10^160. Let's call   this number L. L is ridiculously huge but what's  absolutely essential is that it's a constant,   it doesn't depend on the length of the input  number that we want to factor. It only depends   on the source code of your program. OK, so what  happens next? In each subsequent iteration,   we simulate one step of your program so if it  takes f(n) steps to finish, we'll need to do   that many additional iterations of universal  search to simulate your program to completion.   Since your program factors the number correctly,  at this point Universal search will definitely   terminate. Of course, it might also terminate  even earlier, because of some other factoring   program that has already finished. So what's  the total number of steps that we need to make?   Well, look at this triangle diagram. It shows how  many steps were simulated in total. Of course,   some of the simulated programs may have finished  much earlier, but in the worst case, the time   complexity of Universal search is proportional  to the number of dots in this picture. Since it   took f(n) iterations to simulate our program, we  started the simulation of another f(n) programs   in the meantime. So, the area of this triangle is  roughly one half of (L + f(n)^2). And remember,   L is just a constant so this is simply O(f(n)^2)  steps. Actually, there is one thing that we swept   under the rug - checking whether the outputs of  the finished programs are correct also takes some   time. Fortunately, if we use the fastest known  algorithms for multiplication instead of the   standard algorithm, the time we spend checking is  negligible. And this finishes the analysis of the   basic version of universal search. But how do we  improve O(f(n)^2) to O(f(n)) as I promised? Well,   you can do that by tweaking the algorithm a  little bit. Instead of simulating exactly one   step of every program, in each iteration  we allocate exponentially more steps for   older programs. The complexity of this improved  Universal search becomes roughly 2^L times f(n)   which is even more ridiculous than before, but  Big O can hide big constants, so it's O(f(n)).   This is also how we implemented Universal  search in our code. Speaking of implementation,   there is a tiny difference between our code and  our explanation. Since we wanted to make our code   readable, we didn't want to go through simulating  all Python programs. So we asked Chat GPT and   it told us about this amazing high-powered  language called brain [ __ ] which is also   so simple that we could write its interpreter.  The rest of the code has two classes. Universal   search implements the whole functionality of our  algorithm that doesn't depend on which problem   we're actually trying to solve, and the class  Universal factorization inherits from Universal   search and implements the only problem dependent  part - checking if the output of a simulated   program is correct. I hope this makes it clear  exactly how general the idea of universal search   is. For example, let's say we want to solve  another classical problem - sorting. Then,   we just need to write a new checking function for  sorting and, voila, we now have an asymptotically   optimal algorithm for sorting. In general, the  only property of the problem that we're using is   that there exists a linear time algorithm that  can check if a proposed solution is correct. So this was Levin's Universal search and I expect  many of you might now be a little bit confused   about how to understand it. So let me finish with  a bunch of thoughts about what the lessons to   take away from it are. First of all, what I don't  want you to take away from this is that asymptotic   complexity is a broken concept. Let's say that  we want to analyze some algorithm. There is a   bunch of approaches that we could take. First, you  could code the algorithm and empirically measure   how fast it is as a function of input size. Or you  can just compute the asymptotic complexity. Or,   if you're a hardcore theoretician, you can  just check whether it runs in polynomial time   on a Turing machine. You can see how these  options get increasingly more abstract and   easier to work with. On one extreme, analyzing  an algorithm empirically is usually quite tricky,   because there are a lot of details that you need  to get right. Computing asymptotic complexity is   usually reasonably easy and determining whether an  algorithm runs in polynomial time is often obvious   just by looking at it. But as these concepts get  more abstract, they also get less informative.   Just knowing whether an algorithm runs in  polynomial time doesn't really tell us that much   about it. Asymptotic complexity tells you quite  a lot about an algorithm but in many cases, like   when you need to choose one out of several sorting  algorithms with the same complexity, you'll really   need to sit down and do some empirical testing.  And so you can see that asymptotic complexity   often lies in the sweet spot - it's usually quite  easy to compute, while still being informative.   This makes it the right level of abstraction  for many problems. And sure, it doesn't capture   that some algorithms like Universal search have  really large constants that it hides, but most of   the time it's just fine. Asymptotic complexity  is just a model that computer scientists use,   similar to physicists using frictionless surfaces  that don't actually exist. All models are wrong,   but some of them are useful. But let's go back to  Universal search. Apart from being really weird,   is it actually useful for anything? Well, already  the fact that it is weird means that knowing it   can help you quickly disprove conjectures and  build intuition. It is similar to all those weird   functions you might know from calculus class like  this one, or that one, or this one. All of these   are really weird and it's good to have them in the  back of your mind. And the same goes for Universal   search. But there is also one direct application  of Universal search, albeit a very theoretical   one. If you think about a concrete problem like  factoring, a priori it's not even clear whether   there exists an asymptotically optimal algorithm.  Why can't we just have a sequence of faster   and faster algorithms without there being an  asymptotically fastest one? Although it's possible   to construct some absolutely unhinged problems  where this does happen, in practice that's not   the case. And the reason is the optimal algorithm  is Universal search. So that's why in practice   you don't get a sequence of faster and faster  algorithms. In any case, I hope you enjoyed our   videos about Universal search - an asymptotically  optimal algorithm for many problems. The content   of this video was extremely subtle, so let us  know if you're confused about anything and if   you enjoyed these less or more than our usual  algorithm explainers. And before I go, there is   two things that I wanted to mention. The first  one is we've set up a Patreon for the channel,   so if you'd like to support us, please check out  the link in the description. As a patron you'll   get beta access to the videos. We'll release  an early version to our patrons and then you   can send us feedback and your suggestions will  make it to the final product. And another thing   is I wanted to quickly plug a project that we've  been working on with a few other friends, namely   impromptu. impromptu is an AI based party game  where you use AI to generate weird images like   cats sword fighting and then the other players  see the image and they try to come up with fake   prompts that might have generated the image. And  then you try to guess which prompt was the real   one. So if that sounds like fun to you, check out  the game, it's linked in the video description,   grab a few friends and give it a go. And with  that I'll see you in the next one bye bye!
Info
Channel: polylog
Views: 128,989
Rating: undefined out of 5
Keywords:
Id: 9ONm1od1QZo
Channel Id: undefined
Length: 14min 40sec (880 seconds)
Published: Tue Apr 04 2023
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.