Paper by Erik D. Demaine

Reference:

Lily Chung and Erik D. Demaine, “Celeste is PSPACE-hard”, Thai Journal of Mathematics, volume 21, number 4, December 2023, pages 671–686.

BibTeX

@Article{Celeste_TJM,
  AUTHOR        = {Lily Chung and Erik D. Demaine},
  TITLE         = {Celeste is {PSPACE}-hard},
  JOURNAL       = {Thai Journal of Mathematics},
  journalurl    = {http://thaijmath.in.cmu.ac.th/index.php/thaijmath},
  VOLUME        = 21,
  NUMBER        = 4,
  MONTH         = {December},
  YEAR          = 2023,
  PAGES         = {671--686},

  comments      = {The paper is also available as <A HREF="https://arXiv.org/abs/2211.11839">arXiv:2211.11839</A> and from <A HREF="https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1538">the journal</A>.},
  withstudent   = 1,
  papers        = {Celeste_TJCDCGGG2021},
}

Abstract:

We investigate the complexity of the platform video game Celeste. We prove that navigating Celeste is PSPACE-hard in five different ways, corresponding to different subsets of the game mechanics. In particular, we prove the game PSPACE-hard even without player input.

Comments:

The paper is also available as arXiv:2211.11839 and from the journal.

Availability:

The paper is available in PDF (844k).

See information on file formats.

[Google Scholar search]

Related papers:

Celeste_TJCDCGGG2021 (Celeste is PSPACE-hard)