お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年6月開催)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [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 Print edition: ISSN 0913-5685  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)
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2019-05-10 15:40:00 
発表時間 25 
申込先研究会 COMP 
資料番号 IEICE-COMP2019-2 
巻番号(vol) IEICE-119 
号番号(no) no.21 
ページ範囲 pp.15-22 
ページ数 IEICE-8 
発行日 IEICE-COMP-2019-05-03 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会