Document

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

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.

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} }

Document

**Published in:** Dagstuhl Reports, Volume 1, Issue 10 (2012)

There is a large gap between mathematical structures and the structures computer implementations are based on. To stimulate research to overcome this---especially for infinitary structures---highly non-trivial problem the Dagstuhl Seminar 11411 ``Computing with Infinite Data: Topological and Logical Foundations'' was held. This report collects the ideas that were presented and discussed during the course of the seminar.

Ulrich Berger, Vasco Brattka, Victor Selivanov, Dieter Spreen, and Hideki Tsuiki. Computing with Infinite Data: Topological and Logical Foundations (Dagstuhl Seminar 11411). In Dagstuhl Reports, Volume 1, Issue 10, pp. 14-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{berger_et_al:DagRep.1.10.14, author = {Berger, Ulrich and Brattka, Vasco and Selivanov, Victor and Spreen, Dieter and Tsuiki, Hideki}, title = {{Computing with Infinite Data: Topological and Logical Foundations (Dagstuhl Seminar 11411)}}, pages = {14--36}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2012}, volume = {1}, number = {10}, editor = {Berger, Ulrich and Brattka, Vasco and Selivanov, Victor and Spreen, Dieter and Tsuiki, Hideki}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.10.14}, URN = {urn:nbn:de:0030-drops-33721}, doi = {10.4230/DagRep.1.10.14}, annote = {Keywords: Exact real number computation, Stream computation, Infinite computations, Computability in analysis, Hierarchies, Reducibility, Topological complexity} }

Document

**Published in:** OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

A random iteration algorithm for graph-directed sets is defined and discussed. Similarly to the Barnsley-Elton's theorem, it is shown that almost all sequences obtained by this algorithm reflect a probability measure which is invariant with respect to the system of contractions with probabilities.

Yoshiki Tsujii, Takakazu Mori, Mariko Yasugi, and Hideki Tsuiki. Random Iteration Algorithm for Graph-Directed Sets. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 245-256, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{tsujii_et_al:OASIcs.CCA.2009.2275, author = {Tsujii, Yoshiki and Mori, Takakazu and Yasugi, Mariko and Tsuiki, Hideki}, title = {{Random Iteration Algorithm for Graph-Directed Sets}}, booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)}, pages = {245--256}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-12-5}, ISSN = {2190-6807}, year = {2009}, volume = {11}, editor = {Bauer, Andrej and Hertling, Peter and Ko, Ker-I}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2275}, URN = {urn:nbn:de:0030-drops-22759}, doi = {10.4230/OASIcs.CCA.2009.2275}, annote = {Keywords: Random iteration algorithms, graph-directed sets, displaying fractals, invariant probability measures} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 4351, Spatial Representation: Discrete vs. Continuous Computational Models (2005)

We explain topological properties of the embedding-based approach to
computability on topological spaces. With this approach, he considered
a special kind of embedding of a topological space into Plotkin's
$T^\omega$, which is the set of infinite sequences of $T = \{0,1,\bot \}$.
We show that such an embedding can also be characterized by a dyadic
subbase, which is a countable subbase $S = (S_0^0, S_0^1, S_1^0, S_1^1, \ldots)$ such that $S_n^j$ $(n = 0,1,2,\ldots; j = 0,1$ are regular open
and $S_n^0$ and $S_n^1$ are exteriors of each other. We survey properties
of dyadic subbases which are related to efficiency properties of the
representation corresponding to the embedding.

Hideki Tsuiki. Dyadic Subbases and Representations of Topological Spaces. In Spatial Representation: Discrete vs. Continuous Computational Models. Dagstuhl Seminar Proceedings, Volume 4351, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{tsuiki:DagSemProc.04351.15, author = {Tsuiki, Hideki}, title = {{Dyadic Subbases and Representations of Topological Spaces}}, booktitle = {Spatial Representation: Discrete vs. Continuous Computational Models}, pages = {1--8}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2005}, volume = {4351}, editor = {Ralph Kopperman and Michael B. Smyth and Dieter Spreen and Julian Webster}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04351.15}, URN = {urn:nbn:de:0030-drops-1376}, doi = {10.4230/DagSemProc.04351.15}, annote = {Keywords: Dyadic subbase , embedding , computation over topological spaces , Plotkin's \$T^\backslashomega\$} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail