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:
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)