| 講演名 | 2019-05-10 格子パズルの困難性 小林 靖明(京大), 末續 鴻輝(京大), 立木 秀樹(京大), 上原 隆平(北陸先端大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では、古典的なパズルの一つである格子パズルの計算量的複雑さを研究する。格子パズルは$2n$枚のスリットの入ったプレートからなり、パズルの目的は、プレートを$ntimes n$の大きさの格子に組み上げることである。格子パズルはパズルのソサエティでは古くから知られているが、理論計算機科学の観点からは研究されたことがない。格子パズルには自然な変種がいくつか考えられるが、こうした変種は、クラスNPに含まれる代表的な計算量クラスを特徴づけられる。特にある自然な変種はグラフ同型性問題を特徴づけることができる。つまり、ある変種は一般にGI完全問題である。著者たちの知る限り、古典的なパズルを用いて、非自明なGI完全問題を示したのはこれが初めてである。スライディングブロックパズル同様、この単純なパズルを用いると、いくつかの代表的な計算量クラスを特徴づけることができる。つまり格子パズルは、こうした計算量クラスに新たな知見を与えてくれる。 |
| 抄録(英) | 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. |
| キーワード(和) | 格子パズル / NP完全性 / GI完全性 / FPTアルゴリズム |
| キーワード(英) | lattice puzzle / NP-completeness / GI-completeness / FPT algorithm |
| 資料番号 | COMP2019-2 |
| 発行日 | 2019-05-03 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2019/5/10(から2日開催) |
| 開催地（和） | 熊本大学 |
| 開催地（英） | Kumamoto University |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) / 瀧本 英二(九州大学) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) / 瀧本 英二(九州大学) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 玉置 卓(京大) / 大舘 陽太(熊本大) / 河村 彰星(九州大学) / 垣村 尚徳(慶應義塾大学) / 泉 泰介(名古屋工業大学) |
| 幹事氏名（英） | Suguru Tamaki(Kyoto Univ.) / Yota Otachi(Kumamoto Univ) / 河村 彰星(九州大学) / 垣村 尚徳(慶應義塾大学) / 泉 泰介(名古屋工業大学) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 格子パズルの困難性 |
| サブタイトル（和） | |
| タイトル（英） | On the Complexity of Lattice Puzzle: |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 格子パズル / lattice puzzle |
| キーワード(2)（和/英） | NP完全性 / NP-completeness |
| キーワード(3)（和/英） | GI完全性 / GI-completeness |
| キーワード(4)（和/英） | FPTアルゴリズム / FPT algorithm |
| 第 1 著者 氏名（和/英） | 小林 靖明 / Yasuaki Kobayashi |
| 第 1 著者 所属（和/英） | 京都大学(略称：京大) Kyoto University(略称：Kyoto Univ) |
| 第 2 著者 氏名（和/英） | 末續 鴻輝 / Koki Suetsugu |
| 第 2 著者 所属（和/英） | 京都大学(略称：京大) Kyoto University(略称：Kyoto Univ) |
| 第 3 著者 氏名（和/英） | 立木 秀樹 / Hideki Tsuiki |
| 第 3 著者 所属（和/英） | 京都大学(略称：京大) Kyoto University(略称：Kyoto Univ) |
| 第 4 著者 氏名（和/英） | 上原 隆平 / Ryuhei Uehara |
| 第 4 著者 所属（和/英） | 北陸先端科学技術大学院大学(略称：北陸先端大) Japan Advanced Institute of Science and Technology(略称：JAIST) |
| 発表年月日 | 2019-05-10 |
| 資料番号 | COMP2019-2 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | COMP-21 |
| ページ範囲 | pp.15-22(COMP), |
| ページ数 | 8 |
| 発行日 | 2019-05-03 (COMP) |