The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions
From MaRDI portal
Publication:1041029
DOI10.1016/j.ic.2009.03.001zbMath1191.68337OpenAlexW1651611482MaRDI QIDQ1041029
Dorothea Baumeister, Jörg Rothe
Publication date: 27 November 2009
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2009.03.001
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Unnamed Item
- 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
- On unique satisfiability and the threshold behavior of randomized reductions
- Complexity theory and cryptology. An introduction to cryptocomplexity.
- 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
- The Boolean Hierarchy I: Structural Properties
- The Boolean Hierarchy II: Applications
- Planar Crossovers
- The complexity of theorem-proving procedures
- Classes of Recursively Enumerable Sets and Their Decision Problems
This page was built for publication: The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions
