The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions

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

zbMATH Keywords

randomized reductionsUnique-2-TRPUnique-3-TRP

Mathematics Subject Classification ID

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