The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions
From MaRDI portal
Publication:3540099
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
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