http://www.economist.com/science/displayStory.cfm?story_id16184
NP or not NP? Oct 31st 2002 From The Economist print edition
Tetris, a popular computer game, turns out to be hard for a reason
TETRIS, a computer game invented in 1984, has sold over 60m copies. It is played by organising a sequence of falling blocks in a rectangular well. If a line of the well fills up, it disappears and the blocks on top of it drop down. When there is no room for further blocks, you lose.
The reason Tetris is so popular is that it is easy to learn but hard to master. Just how hard is shown in a paper that Eric Demaine of the Massachusetts Institute of Technology is about to present to a workshop on computational geometry. Dr Demaine and his colleagues have demonstrated that Tetris belongs to a class of mathematical problems known as NP-complete. It thus joins the “travelling salesman†problem, in which a salesman wishes to find the shortest route between the cities he has to visit. Solving that, or allied problems such as the best way to route airliners or fleets of lorries, or to pack boxes into a warehouse to save space, could save huge sums of money. So solving NP-complete problems is more than just a game.
One characteristic of NP-complete problems is that they get rapidly harder as the number of terms (ie, the number of blocks or cities) increases. There is no practical way to solve such problems if the number of terms is too large. But another characteristic is that if a fast way could be found to solve just one of them, they could all be solved quickly using the same method.
Nobody has yet found such an answer. To do so, a mathematician would have to show that NP-complete problems are equivalent to another class of problem, P problems, in which complexity grows relatively slowly with the number of terms. In mathematical jargon, that would mean showing that P=NP.
Most mathematicians believe that P and NP are not, in fact, equal—although none know how to prove that, either. For the lucky person who manages to prove either that P=NP or, contrariwise, that it doesn’t, a prize of $1m awaits, courtesy of the Clay Mathematics Institute.
Few mathematicians are betting their futures on finding any such proof. Instead, their efforts are focused on techniques for NP-complete problems that would yield good (but not perfect) solutions for most cases, a field of study aptly known as approximation theory. Even if the mathematical consensus is right, though, it may eventually be possible to solve NP problems quickly. Several theorists have proposed using quantum computers, if and when such things are built, to do so. These computers would bring some of the weirder effects of quantum theory to bear on the matter—including, according to some physicists, an ability to borrow computing power from parallel universes. What a game of Tetris would be like on a quantum computer is anybody’s guess.
———–