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:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)