For over 15 years, millions of people have spent and wasted their time on the computer game Tetris, in which players must try to place different-shaped bricks that float down the computer screen on to a board. The game’s aim is to cover the board leaving the smallest number of gaps, which can be achieved by rotating bricks or moving them sideways until the screen is filled all the way to the top.

A group of computer scientists at the Massachusetts Institute of Technology (MIT) discovered that Tetris is far more than just a fascinating computer game, however. In October 2002, Eric Demaine, Susan Hohenberger, and David Liben-Nowell proved that Tetris belongs to a wellknown class of problems whose solutions require huge amounts of computer time. The most famous of them is the “traveling salesman problem.” A salesman is required to visit a number of cities and wants to do so by the shortest route, without stopping off in any one city more than once. This problem can be solved by computer, but as it turns out, the time required to calculate the route grows exponentially as the number of cities is increased. For that reason this problem belongs to the class of so-called NP problems. These problems differ from P problems, whose calculation time grows at a much slower rate. Problems are said to belong to the P class if they can be solved in an amount of time that is proportional to a polynomial (hence the letter P).

In theory, NP problems could also be solved in polynomial time. But for this to actually happen, one would need a so-called nondeterministic machine (hence the name of the problem: NP stands for nondeterministic polynomial). But such machines, for example, the much-vaunted quantum computers, do not exist and possibly never will. Hence, computer scientists still search for algorithms that

can solve NP problems in polynomial time. (Is it possible that such algorithms exist but have simply not been found yet? Or maybe the CIA, the M15, or the Mossad already use them to decipher codes and just don’t let on?)

In the meantime, some consolation might be gained from the fact that when tackling an NP problem, one can at least verify possible solutions in polynomial time. For example, seeking the prime factors of 829,348,951 belongs to the class of NP problems. But verifying that 7,919 is one of the prime factors is only a P problem. All one has to do is divide the larger number by the smaller number and verify that nothing is left over. This is possible in polynomial time.

The first theoretical advance toward answering the above question was made when Stephen Cook, a computer scientist at the University of Toronto, proved in 1971 that all NP problems are mathematically equivalent to each other. This means that if only one NP problem can be solved in polynomial time, all NP problems can be solved in polynomial time. This would imply that all NP problems belong to the P class, a relationship that computer scientists express in the concise formula P = NP. Whether this equation will hold remains an open question. Numerous scientists have wrestled with it, not least because the Clay Foundation has offered a $1 million prize for a correct solution.

Today’s computer scientists are still a long way from solving the P versus NP problem. In the meantime they keep themselves occupied with somewhat less challenging problems, such as Tetris. What the MIT researchers discovered was that Tetris is an NP problem. They proved it by reducing the game to the so-called three-partition problem, which has been known since 1979 to be an NP problem.

In this problem a set of numbers must be separated into three separate groups such that the sums of all groups are equal. In their proof, Demaine, Hohenberger, and Liben-Nowell started off with a very complex Tetris position. They proved that, starting with this situation, filling the game board is tantamount to the solution of a three-par-

tition problem. Thus Tetris belongs to the long list of NP problems, as does also, for example, the game Minesweeper that is bundled together with Microsoft Windows. Proof that Minesweeper belongs to the class of NP problems was provided in the year 2000, by Richard Kaye from the University of Birmingham in England.

This does not in any way, however, bring us any closer to the solution of the fundamental problem. Only when an algorithm that detects mines in Minesweeper or fills the Tetris board in polynomial time is found can the $1 million prize be claimed. For now the question remains:

P = NP?