HIROIMONO Is NP-Complete

DOI10.1007/978-3-540-72914-3_5MaRDI QIDQ5426013zbMATH OpenOpenAlexFDO

Authors Daniel Andersson

Publication date 15 November 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-72914-3_5

Mathematics Subject Classification ID

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

Recommendations

• NP-completeness of two pencil puzzles: Yajilin and Country Road
• Bust-a-Move/Puzzle Bobble is NP-complete
• Strategy and Complexity of The Game of Squares
• Pushing blocks is hard.
• Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity

Cited in

(7)

• Rikudo is NP-complete
• Bust-a-Move/Puzzle Bobble is NP-complete
• Tatamibari is NP-complete
• Computational complexity of puzzles and related topics
• Physically verifying the first nonzero term in a sequence: physical ZKPs for ABC End View and Goishi Hiroi
• Verifying the first nonzero term: physical ZKPs for ABC end view, Goishi Hiroi, and Toichika
• NP-completeness and physical zero-knowledge proofs for Zeiger

This page was built for publication: HIROIMONO Is NP-Complete

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