Computational Complexity of Game Boy Games
Hayder Tirmazi, Ali Tirmazi, Tien Phuoc Tran · 2024
Read Computational Complexity of Game Boy Games by Hayder Tirmazi, Ali Tirmazi, Tien Phuoc Tran (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15469.txt.
Description
Video games can hide hard math: a puzzle that looks playful may be as tough as the classic hard problems of computer science. Hayder Tirmazi and two co-authors prove that point in 2024 for games made for the Nintendo Game Boy. They study stretched out versions of four well loved titles, including Donkey Kong and Harvest Moon GB.
For each game they give fresh proofs that winning, or finishing a level, is NP-hard. The proofs translate four famous hard problems into game situations, step by step. Two more games, Lock 'n' Chase and The Lion King, are shown to follow from known results. The work adds the small handheld's shelf to the map of provably hard games.
Catalog record
| CREATOR | Hayder Tirmazi, Ali Tirmazi, Tien Phuoc Tran |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-15469