Friday, 1. November 2002
Topic: - on November 1, 2002 at 11:38:52 PM CET
Tetris, a popular computer game, turns out to be hard for a reason
NP or not NP?
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.
Dr Demaine and his colleagues have demonstrated that Tetris belongs to a class of mathematical problems known as NP-complete.
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.
... Comment
