Computational complexity of cast puzzles

DOI10.1007/978-3-642-10631-6_14MaRDI QIDQ3652198zbMATH OpenOpenAlexFDO

Authors C. Iwamoto, Kento Sasaki, Kenji Nishio, Kenichi Morita

Publication date 17 December 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-10631-6_14

Mathematics Subject Classification ID

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

Recommendations

• A polynomial-time reduction from the 3SAT problem to the generalized string puzzle problem
• Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
• Wooden Geometric Puzzles: Design and Hardness Proofs
• Wooden geometric puzzles: Design and hardness proofs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation

Cited in

(4)

• On a theorem of Razborov
• Mathematical characterizations and computational complexity of anti-slide puzzles
• Mathematical characterizations and computational complexity of anti-slide puzzles
• Computational complexity of puzzles and related topics

This page was built for publication: Computational complexity of cast puzzles

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