Skip Navigation

Home Projects Publications Archives About Sign Up or Log In

Tetris is Hard, Even to Approximate

Although the Tetris video game may not seem like a normal topic of study for three MIT researchers, it served as the basis for an interesting paper that the group submitted to two conferences, as well as attracting the attention of news publications like Science News and Scientific American. The paper, which mathematically proves the computational complexity of the game, can be downloaded from this Web site. The authors used over 50 pages, including appendices, to formulate the problem and derive several necessary theorems. Links to the online news articles that discuss this unusual work are also provided on this site.
?  Cumulative Rating: (not yet rated)
Alternate Title Paper by Erik D. Demaine
Data Type
Scout Publication
Date of Scout Publication 2003-10-24
Archived Scout Publication URL

Resource Comments

(no comments available yet for this resource)