講演抄録/キーワード |
講演名 |
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 |