{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T00:39:54Z","timestamp":1782607194593,"version":"3.54.5"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319078892","type":"print"},{"value":"9783319078908","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07890-8_4","type":"book-chapter","created":{"date-parts":[[2014,5,28]],"date-time":"2014-05-28T12:08:51Z","timestamp":1401278931000},"page":"40-51","source":"Crossref","is-referenced-by-count":7,"title":["Classic Nintendo Games Are (Computationally) Hard"],"prefix":"10.1007","author":[{"given":"Greg","family":"Aloupis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erik D.","family":"Demaine","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan","family":"Guo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giovanni","family":"Viglietta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"Cormode, G.: The hardness of the Lemmings game, or Oh no, more NP-completeness proofs. In: Proceedings of the 3rd International Conference on Fun with Algorithms, pp. 65\u201376 (May 2004)"},{"key":"4_CR2","unstructured":"Demaine, E.D., Demaine, M.L., O\u2019Rourke, J.: PushPush and Push-1 are NP-hard in 2D. In: Proceedings of the 12th Annual Canadian Conference on Computational Geometry, pp. 211\u2013219 (August 2000)"},{"key":"4_CR3","unstructured":"Demaine, E.D., Hoffmann, M., Holzer, M.: PushPush-k is PSPACE-Complete. In: Proceedings of the 3rd International Conference on Fun with Algorithms, pp. 159\u2013170 (May 2004)"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-642-13122-6_22","volume-title":"Fun with Algorithms","author":"M. Fori\u0161ek","year":"2010","unstructured":"Fori\u0161ek, M.: Computational complexity of two-dimensional platform games. In: Boldi, P. (ed.) FUN 2010. LNCS, vol.\u00a06099, pp. 214\u2013227. Springer, Heidelberg (2010)"},{"key":"4_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/978-3-642-30347-0_35","volume-title":"Fun with Algorithms","author":"G. Viglietta","year":"2012","unstructured":"Viglietta, G.: Gaming is a hard job, but someone has to do it! In: Kranakis, E., Krizanc, D., Luccio, F. (eds.) FUN 2012. LNCS, vol.\u00a07288, pp. 357\u2013367. Springer, Heidelberg (2012)"},{"key":"4_CR6","series-title":"LNCS","first-page":"345","volume-title":"FUN 2014","author":"G. Viglietta","year":"2014","unstructured":"Viglietta, G.: Lemmings is PSPACE-complete. In: Ferro, A., Luccio, F., Widmayer, P. (eds.) FUN 2014. LNCS, vol.\u00a08496, pp. 345\u2013356. Springer, Heidelberg (2014)"},{"key":"4_CR7","unstructured":"http:\/\/www.mariowiki.com\/Super_Mario_Bros"},{"key":"4_CR8","unstructured":"http:\/\/donkeykong.wikia.com\/wiki\/Donkey_Kong_Country"},{"key":"4_CR9","unstructured":"http:\/\/www.zeldawiki.org\/The_Legend_of_Zelda_(Game)"},{"key":"4_CR10","unstructured":"http:\/\/www.zeldawiki.org\/The_Legend_of_Zelda:_A_Link_to_the_Past"},{"key":"4_CR11","unstructured":"http:\/\/www.metroidwiki.org\/wiki\/Metroid_(game)"},{"key":"4_CR12","unstructured":"http:\/\/spriters-resource.com\/"},{"key":"4_CR13","unstructured":"http:\/\/www.videogamesprites.net\/"},{"key":"4_CR14","unstructured":"http:\/\/www.nesmaps.com\/"},{"key":"4_CR15","unstructured":"http:\/\/www.snesmaps.com\/"},{"key":"4_CR16","unstructured":"http:\/\/tasvideos.org\/GameResources\/NES\/SuperMarioBros.html"},{"key":"4_CR17","unstructured":"Masterjun. SNES Super Mario World (USA) \u201cglitched\u201d in 02:36.4 (2012), \n                  \n                    http:\/\/www.youtube.com\/watch?v=Syo5sI-iOgY\n                  \n                  \n                 (retrieved April 14, 2012)"}],"container-title":["Lecture Notes in Computer Science","Fun with Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07890-8_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T19:23:27Z","timestamp":1558898607000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07890-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319078892","9783319078908"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07890-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}