Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2009

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: rotation puzzle

Sortuj według:

Ogranicz wyniki do:

Satisfiability Parsimoniously Reduces to the TantrixTM/ Rotation Puzzle Problem

Baumeister D., Rothe J.

Fundamenta Informaticae

2009

Vol. 91, nr 1

35-51

Holzer and Holzer [10] proved that the TantrixTM/ 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 TantrixTM/ rotation puzzle problem. In particular, this reduction preserves the uniqueness of the solution, which implies that the unique TantrixTM/ 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.