[Computational Complexity] The Rubik's Cube Conjecture PROVEN! (Do we care?)
- In 1994 Fermat's last theorem was proven! In 2003 Poincare's conjecture was proven! In 2010 the Rubik Cube Conjecture was proven! That is, it was shown that the minimum number of moves needed to solve Rubik's Cube is 20 (it was known that there are starting configurations that require 20). Here is the pointer: Rubiks Cube has been solved. (Jeff Erickson also had a blog entry on Rubik's cube lately: here.)
We all have a sense that the Rubik Cube result is not as important as the other two. What makes a math problem important?
- Would Martians work on it? I suspect Martians would work on FLT and Poincare but not Rubik's cube. One of the first things I would ask Space Aliens is what Math they have done.
- Does it connect to other parts of mathematics? This leads to a seemingly circular definition of importance: A topic in math is important if it connects to other topics that are interesting. FLT and Poincare's conjecture are connected to other parts of mathematics. One way to understand Rubik's cube is through group theory; however, this is not so much a connection as an application. Rubik's cube studies have not lead to advances in group theory.
- Does the problem have its origins in some real world phenomena? (This is not necessary but helps.)
- The problem should be hard but not so hard that you cannot make any progress on it.
- The proof must be interesting (hmmm- then we need to define interesting).
Posted By GASARCH to Computational Complexity at 9/08/2010 11:55:00 AM