Defying gravity and gadget numerosity: the complexity of the Hanano puzzle

DOI10.1007/978-3-031-34326-1_3MaRDI QIDQ6175086zbMATH OpenOpenAlexFDO

Authors Michael C. Chavrimootoo

Publication date 17 August 2023

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.03400

zbMATH Keywords

computational complexityhardness of gamesirreversible gamesminimizing gadgets

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Using the notion of visibility representations, our paper establishes a new property of instances of the Nondeterministic Constraint Logic (NCL) problem (a PSPACE-complete problem that is very convenient to prove the PSPACE-hardness of reversible games with pushing blocks). Direct use of this property introduces an explosion in the number of gadgets needed to show PSPACE-hardness, but we show how to bring that number from 32 down to only three in general, and down to two in a specific case! We propose it as a step towards a broader and more general framework for studying games with irreversible gravity, and use this connection to guide an indirect polynomial-time many-one reduction from the NCL problem to the Hanano Puzzle -- which is NP-hard -- to prove it is in fact PSPACE-complete.

Recommendations

• scientific article; zbMATH DE number 5734572
• Gadgets and anti-gadgets leading to a complexity dichotomy
• Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
• A gravitational puzzle
• On the complexity of jelly-no-puzzle
• The Complexity of Complexity
• THE PUZZLE OF GRAVITATION

Cites work

• \textsc{Hanano} puzzle is \textsf{NP}-hard
• A unified approach to visibility representations of planar graphs
• Games, puzzles, and computation
• Handbook of graph drawing and visualization
• scientific article; zbMATH DE number 1944412 (Why is no real title available?)
• On the complexity of jelly-no-puzzle
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Super Mario Bros. is harder/easier than we thought
• TETRIS IS HARD, EVEN TO APPROXIMATE
• Walking through doors is hard, even without staircases: proving PSPACE-hardness via planar assemblies of door gadgets

Cited in

(4)

• Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle and beyond
• On the computational complexity of pushing machine
• Friends-and-strangers is \textsf{PSPACE}-complete

This page was built for publication: Defying gravity and gadget numerosity: the complexity of the Hanano puzzle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6175086)