Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem

Simple item page
dc.creatorBaumeister, Dorothea
dc.creatorRothe, Joerg
dc.date2007-05-07
dc.date2008-06-09
dc.date.accessioned2026-07-07T09:42:57Z
dc.date.available2026-07-07T09:42:57Z
dc.descriptionHolzer 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.
dc.description19 pages, 16 figures, appears in the Proceedings of "Machines, Computations and Universality" (MCU 2007)
dc.identifierhttps://arxiv.org/abs/0705.0915
dc.identifierhttp://arxiv.org/abs/0705.0915
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/162377
dc.subjectComputational Complexity
dc.subjectF.1.3; F.2.2
dc.titleSatisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem
dc.typetext

Files

Collections

arXiv