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

DOI10.1016/J.IPL.2024.106520zbMATH Open1547.68255MaRDI QIDQ6602331

Michael C. Chavrimootoo

Publication date: 11 September 2024

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexityhardness of gamesirreversible gamesminimizing gadgets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic game theory and complexity (91A68)

Cites Work

• A unified approach to visibility representations of planar graphs
• \textsc{Hanano} puzzle is \textsf{NP}-hard
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• On the complexity of jelly-no-puzzle
• TETRIS IS HARD, EVEN TO APPROXIMATE
• Super Mario Bros. Is Harder/Easier than We Thought
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle
• Walking through doors is hard, even without staircases: proving PSPACE-hardness via planar assemblies of door gadgets
• Multi-robot motion planning of \(k\)-colored discs is PSPACE-hard
• Pushing blocks via checkable gadgets: PSPACE-completeness of push-1f and block/box dude
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

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

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