Thursday, April 09, 2009

Rubik's Progress

How quickly is maths improving? Say you look at how good your best solution to certain problems is over time. You can estimate how much improvement there is in maths over this time. Most of maths is based around proofs which are pretty hard to measure the quality of. But by looking at applied results you might get evidence to how much the pure maths knowledge has improved also.
So take the example of optimal algorithms for Rubik's cubes (most of this data taken from here).

Start 1974 until now how many face turns are needed to solve the Rubik's cube in the worst case?

52 moves 1981 using Thistlethwaite's Algorithm
42 moves 1990 Kloosterman (doc)
39 moves Mike Reid (i'm trying to get a date for this)
29 moves 1995."In 1995 Michael Reid proved that using these two groups every position can be solved in at most 29 face turns"
27 moves 2006, Silviu Radu
26 moves August 2007, Daniel Kunkle and Gene Cooperman
25 Moves Mar 2008 Tomas Rokicki
23 moves Jun 2008 Tomas Rokicki
22 moves August 2008 Tomas Rokicki

This implies 20 moves are enough using the given algorithm but it has not been proved

Now the best possible solution is at least 20 moves (known as gods algorithm). This number used to be 18 but was improved in 1995 by Michael Reid. The bounds on solutions to the Rubik's cube is improving from two sides. The ability to solve a Rubiks cube going from 52 to 22 moves does not seem earth shattering. There are probably more important maths calculations that have improved over time though. Can you think of any? As usual if you have any more information or corrections I will add them.

No comments:

Post a Comment