2007/05/07 by Dorothea Baumeister, Baumeister, Dorothea, Joerg Rothe +1
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.1.3 #F.2.2 #FOS: Computer and information sciences #Topological and Geometric Data Analysis #cs.CC
paper · pdf · doi:10.48550/arxiv.0705.0915
19 pages, 16 figures, appears in the Proceedings of "Machines, Computations and Universality" (MCU 2007)
openalex publication_date 2007/05/07 · arxiv created 2008/06/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Holzer and Holzer (Discrete Applied Mathematics 144(3):345--358, 2004) proved that the Tantrix(TM) rotation puzzle problem is NP-complete. They also showed that for infinite rotation puzzles, this problem becomes undecidable. We study the counting version and the unique version of this problem. We prove that the satisfiability problem parsimoniously reduces to the Tantrix(TM) rotation puzzle problem. In particular, this reduction preserves the uniqueness of the solution, which implies that the unique Tantrix(TM) rotation puzzle problem is as hard as the unique satisfiability problem, and so is DP-complete under polynomial-time randomized reductions, where DP is the second level of the boolean hierarchy over NP.