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

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

2007-05-07

arxiv.org/abs/0705.0915v2

Computer Science

Computational Complexity

19 pages, 16 figures, appears in the Proceedings of "Machines, Computations and Universality" (MCU 2007)

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-598674