Volume 12, Number 19, November 2022

Classifying Celeste as NP Complete

  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.