| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2019-05-10 15:40 格子パズルの困難性 小林靖明・末續鴻輝・立木秀樹（京大）・○上原隆平（北陸先端大）  COMP2019-2 |
|
| 抄録 | （和） | 本稿では、古典的なパズルの一つである格子パズルの計算量的複雑さを研究する。 格子パズルは$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 / / / / | |
| 文献情報 | 信学技報, vol. 119, no. 21, COMP2019-2, pp. 15-22, 2019年5月. | |
| 資料番号 | COMP2019-2 | |
| 発行日 | 2019-05-03 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2019-2 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2019-05-10 - 2019-05-11 |
| 開催地（和） | 熊本大学 |
| 開催地（英） | Kumamoto University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2019-05-COMP-AL |
| 本文の言語 | 日本語 |
| タイトル（和） | 格子パズルの困難性 |
| サブタイトル（和） | |
| タイトル（英） | On the Complexity of Lattice Puzzle: |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 格子パズル / lattice puzzle |
| キーワード(2)（和/英） | NP完全性 / NP-completeness |
| キーワード(3)（和/英） | GI完全性 / GI-completeness |
| キーワード(4)（和/英） | FPTアルゴリズム / FPT algorithm |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第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) |
| 講演者 | 第4著者 |
| 発表日時 | 2019-05-10 15:40:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2019-2 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | no.21 |
| ページ範囲 | pp.15-22 |
| ページ数 | 8 |
| 発行日 | 2019-05-03 (COMP) |
[研究会発表申込システムのトップページに戻る]