Authors
Zeeshan Ahmed, Alapan Chaudhuri, Kunwar Grover, Ashwin Rao, Kushagra Garg and Pulak Malhotra, International Institute of Information Technology, Hyderabad, India
Abstract
We analyze the computational complexity of the video game "CELESTE" and prove that solving a generalized level in it is NP-Complete. Further, we also show how, upon introducing a small change in the game mechanics (adding a new game entity), we can make it PSPACE-complete.
Keywords
Complexity analysis, NP completeness, algorithmic analysis, game analysis.