Monday, August 30, 2010

Patents as Mutual Assured Destruction

The best way I can understand the popularity of software patents is that they protect incumbent companies from newcomers. Large incumbent companies accumulate patents, they use them to litigate against small newcomers who have no patents of their own, and they form patent-sharing agreements with each other to prevent the same thing from happening to them. Occasionally it comes back to bite one of the incumbents, but for the most part they seem to believe it comes out in their favor.

One place this arrangement fails, though, is if one of the incumbents decides not to play for the long term. See, the reason incumbents don't sue each other over patents is that they fear the counter-suit. It's classic M.A.D.: mutual assured destruction.

However, what if an incumbent is on their way out of the computer business, either because they are shifting focus or because they are retiring? Well, in that case, the fear of a counter-suit would be nonexistent, wouldn't it? Count me in as one who thinks Paul Allen's recent actions suggest he is planning to retire, or at the very least get out of computers. My next best guesses are that he is trying to make some sort of point, or that he is simply unsavvy about the software industry. Neither of these sounds especially likely.

Wednesday, August 11, 2010

Rubik's Cube's difficulty cracked

I'm late to notice this, but recently a team proved that a Rubik's Cube can always be solved in 20 moves or less, regardless of its initial configuration. It had already been proven, back in 1995, that at least one initial configuration requires 20 moves to solve. Thus, all positions can be solved in 20 moves, and some positions require the full 20.

What is particularly interesting is that the these researchers found the 20-move bound by having a computer solve all of the 4E19 initial positions exhaustively. The best proof that didn't do an exhaustive search only proved an upper bound of 22 moves.

I wonder if a human-digestible proof will be found for the 20-move upper bound, or if we'll be left with computers generating the stronger proof? At any rate, this is yet one more problem where a mathematical result depends crucially on some very heavy computation.