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

CREATORHayder Tirmazi, Ali Tirmazi, Tien Phuoc Tran
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-15469

Browse the full library · About the Tower of Babel