DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2019.32

On the Complexity of Lattice Puzzles

Authors: Yasuaki Kobayashi, Koki Suetsugu, Hideki Tsuiki, and Ryuhei Uehara

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract

In this paper, we investigate the computational complexity of lattice puzzle, which is one of the traditional puzzles. A lattice puzzle consists of 2n plates with some slits, and the goal of this puzzle is to assemble them to form a lattice of size n x n. It has a long history in the puzzle society; however, there is no known research from the viewpoint of theoretical computer science. This puzzle has some natural variants, and they characterize representative computational complexity classes in the class NP. Especially, one of the natural variants gives a characterization of the graph isomorphism problem. That is, the variant is GI-complete in general. As far as the authors know, this is the first non-trivial GI-complete problem characterized by a classic puzzle. Like the sliding block puzzles, this simple puzzle can be used to characterize several representative computational complexity classes. That is, it gives us new insight of these computational complexity classes.

Cite as

Yasuaki Kobayashi, Koki Suetsugu, Hideki Tsuiki, and Ryuhei Uehara. On the Complexity of Lattice Puzzles. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 32:1-32:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2019.32,
  author =	{Kobayashi, Yasuaki and Suetsugu, Koki and Tsuiki, Hideki and Uehara, Ryuhei},
  title =	{{On the Complexity of Lattice Puzzles}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{32:1--32:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.32},
  URN =		{urn:nbn:de:0030-drops-115287},
  doi =		{10.4230/LIPIcs.ISAAC.2019.32},
  annote =	{Keywords: Lattice puzzle, NP-completeness, GI-completeness, FPT algorithm}
}

Search Results

Documents authored by Suetsugu, Koki

On the Complexity of Lattice Puzzles

Abstract

Cite as

Thanks for your feedback!

Could not send message