What do the Rubik's cube and a cipher from the 70s have in common? Let's find out. Our Patreon: https://www.patreon.com/Polylog 0:00 Rubik's cube 9:40 DES ------------------------ Links: Feliks setting the 4.73 record https://www.youtube.com/watch?v=R07JiT0PlcE webpage "God's number is 20" http://www.cube20.org/ The fact it was verified computationally that every cube can be solved in at most 20 moves is super impressive and much more complicated than the problem of solving just one cube that we covered in this video! Four degrees of separation on Facebook https://arxiv.org/pdf/1111.4570.pdf Code: https://github.com/polylog-cs/rubiks-cube-video/blob/main/code/rubik_mitm_solution.cpp ------------------------ Fill in the gaps: Convince yourself that the meet in the middle algorithm finds the shortest path! Convince yourself that the meet in the middle algorithm for Rubik's cube does not need to know that every cube can be solved in 20 steps. ------------------------ Real Algorithms: The first algorithms solving a random scramble like Korf's algorithm https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf work roughly as follows: First, although there are around 10^20 possible cube configurations, if you focus on just the possible configurations of 8 corner cubies, the number of possibilities drops to around 10^8. Using breadth first search, you can precompute for each such configuration of corner cubies how many steps you need to put them into the correct position. You need at least that many steps to solve the full cube configuration, probably even more as you need to solve not just the corners but also the edges. You can now iterate a breadth first search from your scrambled cube, each time looking into further distance from it. For each cube you look up in your table of size 10^8 to find how many steps, at least, are needed to finish the search. If it is more than the current maximum distance you are looking at, you stop searching, as you can be sure you will not find the solved cube in this branch of the breadth first search. This approach is similar to the meet in the middle algorithm in that we first precompute some information from the solved cube and then run breadth first search from the scrambled cube. However, now you need much less memory. The actual state of the art algorithms are more complicated than that. You can read more about it e.g. here. https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik%27s_Cube ------------------------ More Connections: The meet in the middle trick is also called "bidirectional search" in the context of searching graphs. https://en.wikipedia.org/wiki/Bidirectional_search Computing the exact number of states of a Rubik's cube (we used it is around 10^20) is not so hard. https://www.youtube.com/watch?v=z2-d0x_qxSM The graphs where the number of nodes in your distance grows exponentially are pretty important in computer science. For example, there are scale-free networks and expander graphs. https://en.wikipedia.org/wiki/Scale-free_network https://en.wikipedia.org/wiki/Expander_graph Triple DES is kind of a hack made to prolong the life of the DES cipher when it became apparent that it is not strong enough. However, because of the meet in the middle attack, its "security level" is only 2*56 bits and not 3*56 bits as one would naively expect. But you still need to apply DES three times. So you can guess it is not the most efficient way of doing the encryption; it is now superseded by the so-called AES standard. https://en.wikipedia.org/wiki/Advanced_Encryption_Standard ------------------------ Riddles: If you like to solve algorithmic puzzles, here you can find more algorithmic problems that can be solved with this technique: https://www.youtube.com/watch?v=18sJ3mK173s https://wiki.algo.is/Meet-in-the-middle Try to prove, just with pen, paper and calculator that there is a cube for which at least 16 moves are needed to solve it. Try to convince yourself that by blind search of the cube graph you cannot beat the sqrt(N) time, at least if you do not use anything else than that the graph "looks random". Hint: Birthday paradox ------------------------ Attributions: To make this video, we used manim, a Python library: https://docs.manim.community/en/stable/ The color palette we use: https://ethanschoonover.com/solarized/ Photo of Grant Sanderson: null Thumbnail: Alžběta Volhejnová