
Probably Google's App Engine
http://code.google.com/appengine/
It is unlikely to be anything else.
Has Google finally cracked it? Revealed today, courtesy of the massed ranks of Google computing, the answer to the ultimate question – not the old one about Life the Universe and Everything – is 20! We’re talking God’s Number here, or more prosaically the maximum number of moves required to solve the Rubik's Cube no matter …
Neither Thistlethwaite nor Kloosterman claimed that the diameter of the Cayley graph of the Rubik-cube group -- the minimum number of moves required to solve any position -- is their respective number, merely that it was *at most* that. Thus, contrary to the implications of the article, they weren't wrong.
Also, "...2.2 billion groups, known as cosets..." this is really really bad. Use collections or some other synonym rather than groups, because these cosets themselves lie in a group (in the technical sense of the word).
Finally, this is a dull problem which, now that it has been finally solved, can be safely ignored for the rest of time. This differs from the P = NP problem in this respect, as well as this solution being probably true and the P = NP solution being probably false.
Well, you can brute-force this problem instance, so it's definitely known now, in the same ways as the four-colour theorem.
I remember at least two papers by Douglas Hofstaedter on Rubik's cube. They are probably only available on the Dark Internet, but if not, links would be appreciated.
I believe they are referring to the local maximum; when you consider only the set of minimum moves required to solve all given possible initial states of a Rubik's cube, 20 is the maximum value of that set.
If they were talking minimums, that value is 0; if the Rubik's cube's initial state is already solved, then you do not have to make any moves to get it to a solved state. Not only that, but both you and I could successfully solve it, given that particular initial state.
They figured out a way to figure out the maximum number of steps to figure out a puzzle.
I'd just like to say without a trace of sarcasm that I am mightilty impressed by these people.
Oh, and @Daniel B., it's the maximum of minima. The minimum is zero, or one if you exclude already solved starting states.
Doesn't work unless they're dumb people who just learnt the moves. Someone did this in the Maths coffee bar in 1982 and everyone recognised what had been done while solving the cube.
David Singmaster wrote an interesting note about the Cube and Group Theory about that time.
If you're bored of just solving it then get someone to randomly make 5 or so moves and then try and get in back in the same number of moves.
so is rubik's cube polynomial-time after all? Everyone seems to say it's NP-complete, yet the algorithms in the books/pamphlets that were produced at the time give bounded time ways of solving it, now it looks as though the upper bound / the degree of the polynomial is 20?
Hence we may be proving that in fact P = NP rather than P != NP :-D
Rubik's cube is a finite problem. NP and P deals with problems that vary with some input. For example, with factorizing numbers*, how long it takes you to do depends on how big the numbers are. Rubik's cube is 3x3x3, and is fixed. You can consider n x n x n Rubik's cubes, and ask whether there is a polynomial-time (in n) algorithm to solve them. My guess is yes, but I cannot be bothered to prove this or even look it up, because nobody cares.
*although it's NP but not necessarily NP-complete (in fact, I can't remember whether it is known to not be)
It's obvious:
2πn^(n - 2) + 1 for n > 1
where n, is the number of tiles on a side:
3 x 3 x 3 = 2.π.3^1 + 1 = 19.85 (20 whole moves)
and so on:
4 102
5 786
6 8144
7 105602
8 1647100
9 30052282
10 628318532
PS a 2x2 cube can be done in 7 moves.
Mine's the one with the Fortean Times in the pocket
First!
Oops, sorry!
First you ask "How many mathematicians does it take to screw in a light bulb?"
The answer to that is 2 (or more), given a) a sufficiently large lightbulb or b) sufficiently small mathematicians, given of course that it takes two to (ahem) tango, and given non-Hermaphroditic mathematicians. NB I'm assuming that mathematicians would generally prefer a bed and not a lightbulb, but I have no proof of that.
Subsequently, you go on about changing a lightbulb. I humbly suggest that changing a light bulb is not the same as screwing in a light bulb. So whilst it may have been shown that "for all n in the positive integers, n mathematicians can change a light bulb.", that is not the answer to "How many mathematicians does it take to screw in a light bulb?"
QED!