情報処理学会 第84回全国大会 会期:2022年3月3日~5日 情報処理学会 第84回全国大会 会期:2022年3月3日~5日

6K-02
Kirby is PSPACE-complete
○太田涼平,伊藤大修,山中克久,平山貴司(岩手大)
Recently, the computational complexity of video games have been analyzed. In this paper, we focus on Kirby which is one of popular video games in Japan. We investigate the computational complexity of Kirby. We prove PSPACE-completeness of Kirby by applying the general framework proposed by Aloupis et al., for proving PSPACE-hardness.