Satisfiability Parsimoniously Reduces to the Tantrix^TM/ Rotation Puzzle Problem

• Autorzy: Baumeister D. , Rothe J.
• Języki publikacji: EN

Abstrakty

EN

Holzer and Holzer [10] 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.

Słowa kluczowe

EN

computational complexity; rotation puzzle; tiling of the plane; parsimonious reduction; counting problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 1
• Strony: 35--51
• Opis fizyczny: bibliogr. 18 poz., wykr.

Twórcy

autor

Baumeister D.

autor

Rothe J.

• Institut für Informatik Heinrich-Heine-Universität Düsseldorf 40225 Düsseldorf, Germany,

Bibliografia

• [1] Barbanchon, R.: On Unique Graph 3-Colorability and Parsimonious Reductions in the Plane, Theoretical Computer Science, 319(1-3), 2004, 455-482.
• [2] Baumeister, D., Rothe, J.: Satisfiability Parsimoniously Reduces to the TantrixTM Rotation Puzzle Problem, Proceedings of the 5th Conference on Machines, Computations and Universality, Springer-Verlag Lecture Notes in Computer Science #4664, pages 134-145, September 2007.
• [3] Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., Wechsung, G.: The Boolean Hierarchy I: Structural Properties, SIAM Journal on Computing, 17(6), 1988, 1232-1252.
• [4] Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., Wechsung, G.: The Boolean Hierarchy II: Applications, SIAM Journal on Computing, 18(1), 1989, 95-111.
• [5] Cai, J.,Meyer, G.: GraphMinimal Uncolorability is DP-complete, SIAM Journal on Computing, 16(2), April 1987, 259-277.
• [6] Chang, R., Kadin, J., Rohatgi, P.: On Unique Satisfiability and the Threshold Behavior of Randomized Reductions, Journal of Computer and System Sciences, 50(3), 1995, 359-373.
• [7] Cook, S.: The complexity of theorem-proving procedures, Proceedings of the 3rd ACM Symposium on Theory of Computing, ACM Press, pages 151-158, 1971.
• [8] Goldschlager, L.: The Monotone and Planar Circuit Value Problems are log Space Complete for P, SIGACT News, 9(2), 1977, 25-29.
• [9] Grädel, E.: Domino Games and Complexity, SIAM Journal on Computing, 19(5), 1990, 787-804.
• [10] Holzer, M., Holzer, W.: TantrixTM rotation puzzles are intractable, Discrete Applied Mathematics, 144(3), 2004, 345-358.
• [11] McColl, W.: Planar Crossovers, IEEE Transactions on Computers, C-30(3), 1981, 223-225.
• [12] Papadimitriou, C.: Computational Complexity, Addison-Wesley, 1994.
• [13] Papadimitriou, C., Yannakakis, M.: The Complexity of Facets (and some Facets of Complexity), Journal of Computer and System Sciences, 28(2), 1984, 244-259.
• [14] Riege, T., Rothe, J.: Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems - a Survey, Journal of Universal Computer Science, 12(5), 2006, 551-578.
• [15] Rothe, J.: Exact Complexity of Exact-Four-Colorability, Information Processing Letters, 87(1), July 2003, 7-12.
• [16] Rothe, J.: Complexity Theory and Cryptology. An Introduction to Cryptocomplexity, EATCS Texts in Theoretical Computer Science, Springer-Verlag, Berlin, Heidelberg, New York, 2005.
• [17] Valiant, L.: The Complexity of Computing the Permanent, Theoretical Computer Science, 8(2), 1979, 189-201.
• [18] Valiant, L., Vazirani, V.: NP is as Easy as Detecting Unique Solutions, Theoretical Computer Science, 47, 1986, 85-93.