The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions

DOI10.1007/978-3-540-88282-4_9zbMath1156.68390MaRDI QIDQ3540099

Jörg Rothe, Dorothea Baumeister

Publication date: 20 November 2008

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-88282-4_9

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions, The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• The complexity of facets (and some facets of complexity)
• NP is as easy as detecting unique solutions
• TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable
• Domino Games and Complexity
• The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions
• Satisfiability Parsimoniously Reduces to the TantrixTM Rotation Puzzle Problem
• Planar Crossovers
• The complexity of theorem-proving procedures