| Presentation | 2019-05-10 On the Complexity of Lattice Puzzle: Yasuaki Kobayashi, Koki Suetsugu, Hideki Tsuiki, Ryuhei Uehara, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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 $ntimes 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 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | lattice puzzle / NP-completeness / GI-completeness / FPT algorithm |
| Paper # | COMP2019-2 |
| Date of Issue | 2019-05-03 (COMP) |
| Conference Information | |
| Committee | COMP / IPSJ-AL |
|---|---|
| Conference Date | 2019/5/10(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Kumamoto University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshihiro Fujito(Toyohashi Univ. of Tech.) / 瀧本 英二(九州大学) |
| Vice Chair | Shinichi Nakano(Gunma Univ.) |
| Secretary | Shinichi Nakano(Kyoto Univ.) / (Kumamoto Univ) |
| Assistant | Kazuhisa Seto(Seikei Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On the Complexity of Lattice Puzzle: |
| Sub Title (in English) | |
| Keyword(1) | lattice puzzle |
| Keyword(2) | NP-completeness |
| Keyword(3) | GI-completeness |
| Keyword(4) | FPT algorithm |
| 1st Author's Name | Yasuaki Kobayashi |
| 1st Author's Affiliation | Kyoto University(Kyoto Univ) |
| 2nd Author's Name | Koki Suetsugu |
| 2nd Author's Affiliation | Kyoto University(Kyoto Univ) |
| 3rd Author's Name | Hideki Tsuiki |
| 3rd Author's Affiliation | Kyoto University(Kyoto Univ) |
| 4th Author's Name | Ryuhei Uehara |
| 4th Author's Affiliation | Japan Advanced Institute of Science and Technology(JAIST) |
| Date | 2019-05-10 |
| Paper # | COMP2019-2 |
| Volume (vol) | vol.119 |
| Number (no) | COMP-21 |
| Page | pp.pp.15-22(COMP), |
| #Pages | 8 |
| Date of Issue | 2019-05-03 (COMP) |