Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.15469 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910755721314304 |
|---|---|
| author | Tirmazi, Hayder Tirmazi, Ali Tran, Tien Phuoc |
| author_facet | Tirmazi, Hayder Tirmazi, Ali Tran, Tien Phuoc |
| contents | We analyze the computational complexity of several popular video games released for the Nintendo Game Boy video game console. We analyze the complexity of generalized versions of four popular Game Boy games: Donkey Kong, Wario Land, Harvest Moon GB, and Mole Mania. We provide original proofs showing that these games are \textbf{NP}-hard. Our proofs rely on Karp reductions from four of Karp's original 21 \textbf{NP}-complete problems: \textsc{Sat}, \textsc{3-Cnf-Sat}, \textsc{Hamiltonian Cycle}, and \textsc{Knapsack}. We also discuss proofs easily derived from known results demonstrating the \textbf{NP}-hardness of Lock `n' Chase and The Lion King. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_15469 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computational Complexity of Game Boy Games Tirmazi, Hayder Tirmazi, Ali Tran, Tien Phuoc Computational Complexity We analyze the computational complexity of several popular video games released for the Nintendo Game Boy video game console. We analyze the complexity of generalized versions of four popular Game Boy games: Donkey Kong, Wario Land, Harvest Moon GB, and Mole Mania. We provide original proofs showing that these games are \textbf{NP}-hard. Our proofs rely on Karp reductions from four of Karp's original 21 \textbf{NP}-complete problems: \textsc{Sat}, \textsc{3-Cnf-Sat}, \textsc{Hamiltonian Cycle}, and \textsc{Knapsack}. We also discuss proofs easily derived from known results demonstrating the \textbf{NP}-hardness of Lock `n' Chase and The Lion King. |
| title | Computational Complexity of Game Boy Games |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2412.15469 |