Computational Complexity
In computer science, it is common to analyze the computational complexity of problems, including real life problems and games. It was proven that for the offline version of Tetris (in which all the pieces are known in advance) the following objectives are NP-complete:
- Maximizing the number of rows cleared while playing the given piece sequence.
- Maximizing the number of pieces placed before a loss occurs.
- Maximizing the number of simultaneous clearing of four rows.
- Minimizing the height of the highest filled grid square over the course of the sequence.
Also, it is not possible to find a polynomial time approximation algorithm for the first 2 problems and it is hard to approximate the last problem within 2 − ε for every ε > 0.
To prove NP-completeness, it was shown that there is a polynomial reduction between the 3-partition problem, which is also NP-Complete, and the Tetris problem.
Read more about this topic: Tetris
Famous quotes containing the word complexity:
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)