| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2019-05-10 15:40 On the Complexity of Lattice Puzzle: Yasuaki Kobayashi, Koki Suetsugu, Hideki Tsuiki (Kyoto Univ), Ryuhei Uehara (JAIST)  COMP2019-2 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (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) |
| (in English) | lattice puzzle / NP-completeness / GI-completeness / FPT algorithm / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 119, no. 21, COMP2019-2, pp. 15-22, May 2019. | |
| Paper # | COMP2019-2 | |
| Date of Issue | 2019-05-03 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | COMP2019-2 |
|
| Conference Information | |
| Committee | COMP IPSJ-AL |
| Conference Date | 2019-05-10 - 2019-05-11 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Kumamoto University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2019-05-COMP-AL |
| Language | Japanese |
| 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 |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 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) |
| 5th Author's Name | |
| 5th Author's Affiliation | () |
| 6th Author's Name | |
| 6th Author's Affiliation | () |
| 7th Author's Name | |
| 7th Author's Affiliation | () |
| 8th Author's Name | |
| 8th Author's Affiliation | () |
| 9th Author's Name | |
| 9th Author's Affiliation | () |
| 10th Author's Name | |
| 10th Author's Affiliation | () |
| 11th Author's Name | |
| 11th Author's Affiliation | () |
| 12th Author's Name | |
| 12th Author's Affiliation | () |
| 13th Author's Name | |
| 13th Author's Affiliation | () |
| 14th Author's Name | |
| 14th Author's Affiliation | () |
| 15th Author's Name | |
| 15th Author's Affiliation | () |
| 16th Author's Name | |
| 16th Author's Affiliation | () |
| 17th Author's Name | |
| 17th Author's Affiliation | () |
| 18th Author's Name | |
| 18th Author's Affiliation | () |
| Speaker | Author-4 |
| Date Time | 2019-05-10 15:40:00 |
| Presentation Time | 25 minutes |
| Registration for | COMP |
| Paper # | COMP2019-2 |
| Volume (vol) | vol.119 |
| Number (no) | no.21 |
| Page | pp.15-22 |
| #Pages | 8 |
| Date of Issue | 2019-05-03 (COMP) |
[Return to Top Page]