  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.
