Search Results

Documents authored by Khangure, Dylan

Document
DOI: 10.4230/LIPIcs.FUN.2024.18
Advanced Spikes `n' Stuff: An NP-Hard Puzzle Game in Which All Tutorials Are Efficiently Solvable

Authors: Christian Ikenmeyer and Dylan Khangure

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract
We adjust Alan Hazelden’s 2017 polynomial time solvable puzzle game Spikes `n' Stuff: We obtain the NP-complete puzzle game Advanced Spikes `n' Stuff with 3 trap types so that each strict subset of the traps results in a polynomial time solvable puzzle game. We think of this as a "hard game in which all tutorial levels are easy". The polynomial time algorithms for solving the tutorial games turn out to be quite different to each other. While numerous papers analyze the complexity of games and which game objects make a game NP-hard, our paper is the first to study a game where the NP-hardness can only be achieved by a combination of all game objects, assuming P differs from NP.
Cite as

Christian Ikenmeyer and Dylan Khangure. Advanced Spikes `n' Stuff: An NP-Hard Puzzle Game in Which All Tutorials Are Efficiently Solvable. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ikenmeyer_et_al:LIPIcs.FUN.2024.18,
  author =	{Ikenmeyer, Christian and Khangure, Dylan},
  title =	{{Advanced Spikes `n' Stuff: An NP-Hard Puzzle Game in Which All Tutorials Are Efficiently Solvable}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.18},
  URN =		{urn:nbn:de:0030-drops-199265},
  doi =		{10.4230/LIPIcs.FUN.2024.18},
  annote =	{Keywords: computational complexity, P vs NP, motion planning, games}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact