Thursday, March 23, 2006

First we had to factor prime numbers...

and now, we need to factor numbers to generate cryptographic keys... (from "2020 Computing: Champing at the Bits" in Nature magazine's 2020 Future of Computing Web Focus. This kind of pedantic peeve aside, the web focus has some pretty interesting articles.

In fact, quantum computers are currently little more than two-trick wonders. In 1994, Peter Shor, now based at MIT, devised an algorithm that would allow quantum computers to factor numbers exponentially faster than conventional computers. Factorization is important in cryptography, where it is needed to make and break keys. And in 1996, Lov Grover, who is now at Lucent Technologies in Murray Hill, New Jersey, unveiled a quantum algorithm that can greatly speed up database searches.

Break an assumption

Every time I hear or read something about the story of how the Wright brothers built the first airplane, I find it inspiring in a new way. Yesterday, I watched a NOVA program on (the recreation of) the Wright brothers' Model B airplane. Here's an excerpt from the transcript:

TOM CROUCH: The great problem, really, that, uh, flying machine experimenters in the late 19th and early 20th century faced was the issue of control, and it was the Wright brothers' recognition of the fact that the control issue was going to be critical that initially set them apart from virtually everyone else.

NARRATOR: While most engineers assumed that a successful aircraft would need to be inherently stable, as bicycle builders, the Wrights made their living building vehicles which were inherently unstable. They knew that a bicycle was stable only if the rider kept it under control.

TOM CROUCH: Most other experimenters in the field assumed that the control issue was going to be so difficult that the best approach they could take was to build an airplane that had maximum sort of automatic stability, an airplane that would fly in a straight line until the pilot made some sort of control input to change its direction, and then it would continue going in a straight, straight line again.

NARRATOR: Early designers imagined aircraft as a kind of flying boat. If wind or waves rock a boat, it should be able to right itself. Instead of a boat, the Wrights thought of their flying machine more like a bicycle and rider: if the bike rolled to the left or right it was the job of the rider to keep it upright. The Wrights didn't worry about building automatic stability into their airplanes anymore than they designed their bicycles to go without riders.

TOM CROUCH: As cyclists, the Wright brothers said to themselves, "Well, if you tried to describe the act of riding a bicycle to someone who'd never seen one, um, what? You're going to roll down the street in this thing with two narrow rubber tires, and you're going to be balancing while you're operating the handle bars."

It would sound like the sort of feat that only the world's greatest acrobat could accomplish, and yet, they knew that once you learn how to ride a bike, you internalize that, and it becomes perfectly natural and instinctive; you don't even think about it. And they were sure that the same thing would be true of a flying machine.

In other words, they broke an unstated, implicit, assumption that was prevalent in their field. Geniuses often do. In computer science, this is probably a good algorithm design principle - check your assumptions, write them down. The space of possible solutions might include things that you might fail to consider because of your prejudices. Remember the puzzles "place four marbles that are equidistant from each other" and "two Americans were standing in front of the British Embassy in Buenos Aires - one was the son of the other, but the second one was not the father of the first one - how is that possible?"? In each of these, you might have to break an implicit assumption to get to the solution.

Strassen broke an assumption when he used subtractions in a matrix multiplication algorithm, as did Gill/Rabin/Solovay-Strassen/Carter-Wegman with randomized algorithms, and Codd with relational databases.

Aha! Insight by Martin Gardner has more interesting puzzles, some of which call for breaking assumptions.

So, whatever you're doing, go check your assumptions once more.