一般化KaboozleのNP完全性
スポンサーリンク
概要
- 論文の詳細を見る
Kaboozle とはパズルの一種で,数枚の正方形のカードからなる.それぞれのカードの両面には色つきのパスや端点が描かれ,いくつか穴が空けられている.パズルの目的は,すべてのカードを適切な順序と向きで重ねて,特定の色のパスの両端点をその色の 1 本のパスでつなぐことである.カードの裏表・回転・順序という自由度があるので,この問題が一般に NP 完全であることは容易に想像できる.本稿では,これら 3 種類の自由度のどれか 1 つを使うだけで,この問題が NP 完全であることを示す.さらに Kaboozle を全部つなぎ合わせて 1 次元上の問題に制限する.具体的には,すべてのカードを帯状につなぎ合わせ,しかもつなぎ目の山折り/谷折りをすべて指定する.このときカードの回転や裏返しは禁止され,またカードの順序もかなり限定される.そこまで限定しても一般化 Kaboozle は NP 完全問題である.
- 2010-05-12
著者
-
上原 隆平
北陸先端科学技術大学院大学
-
上原 隆平
北陸先端科学技術大学院大学情報科学研究科
-
上原 隆平
駒澤大学自然科学教室
-
上原 隆平
北陸先端科学技術大学情報科学研究科
-
上原 降平
北陸先端科学技術大学院大学情報科学研究科
-
浅野 哲夫
北陸先端科学技術大学院大学 情報科学研究科
-
浅野 孝夫
中央大学理工学部情報工学科
-
浅野 哲夫
北陸先端科学技術大学院大学情報科学研究科
-
ErikD.Demaine
Computer Science and Artificial Intelligence Lab, Massachusetts Institute of Technology (MIT)
-
MartinL.Demaine
Computer Science and Artificial Intelligence Lab, Massachusetts Institute of Technology (MIT)
-
上原 隆平
北陸先端科学技術大学院大学 情報科学研究科
-
浅野 哲夫
北陸先端科学技術大学院大学
関連論文
- 区間二部グラフの効率の良い認識に関する研究 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- NP-completeness of generalized Kaboozle (コンピュテーション)
- Bipartite Permutation Graphのランダム生成と列挙
- 弦グラフおよび弦二部グラフのクラスにおけるマッチングの数え上げ
- 再構成問題の計算複雑さ
- あみだくじの高速列挙
- 折紙の計算量的複雑さの研究 (小特集 折紙工学の現状と課題)
- 折紙の計算量的複雑さの研究(折紙工学の現状と課題)
- Complexity of pleat folding (理論計算機科学の深化と応用--RIMS研究集会報告集)
- Enumeration of Perfect Sequences of Chordal Graph (Acceleration and Visualization of Computation for Enumeration Problems)
- Polygons Folding to Plural Incongruent Orthogonal Boxes (Acceleration and Visualization of Computation for Enumeration Problems)
- Reconstruction of Connected Interval Graphs (Acceleration and Visualization of Computation for Enumeration Problems)
- 2-E-17 Enumeration of Perfect Sequences of Chordal Graph
- じゃばら折りの複雑さに関する研究
- 2-E-6 無限サーバ待ち行列がつくるスケールフリー区間グラフ : クラスタ係数の評価(待ち行列(2))
- 複数の箱を折ることのできる展開図に関する研究
- 折り紙とコンピュータサイエンス(学生/教養のページ)
- コーダルグラフの完全列の列挙
- 2-B-4 無限サーバ待ち行列がつくるスケールフリー区間グラフ(待ち行列(2))
- 区間表現からMPQ-treeを効率よく構成するアルゴリズム
- 区間表現からMPQ-tree を効率よく構成するアルゴリズム(計算機科学の理論とその応用)
- スケールフリーグラフ上における局所情報を用いたランダムウォークについて
- 2部パーミュテーショングラフのバンド幅
- 航空路線問題に対する効率の良いアルゴリズム
- プトレマイオスグラフのラミナー構造とその応用
- ある限られたグラフクラスに対する最長路問題
- 部分ゲートとその同定
- 多くの計算路によって特徴付られる計算量クラス
- 絵画的迷路の作り方 (理論計算機科学の深化と応用)
- 距離遺伝的グラフの木表現とその応用
- コーダルグラフの独立点集合の数えあげ問題
- Canonical Data Structure for Probe Interval Graphs (Evolutionary Advancement in Fundamental Theories of Computer Science)
- プロープ区間グラフの拡張MPQ木表現
- 2部グラフとProbe区間グラフにおける木スパナー
- 2部グラフの部分クラスに対するGI完全性について
- 重み最大マッチングを求める並列近似アルゴリズム
- グラフの連結成分の個数と応用
- 弦グラフの一般化と、そのグラフ上での問題の難しさ
- ある投票ゲームのシミュレーション
- Ptolemaic Graph 上の最長路問題に関する研究(計算機科学の理論とその応用)
- 飛び出す絵本の複雑さ
- 単純多角形の生成に関する発見的手法(セッション2)
- グラフ上のボロノイゲームとその困難性(セッション1)
- 3充足可能性判定問題3SATの単一解を持つ正例題生成手法
- 3充足可能性判定問題 3SAT の単一解を持つ正例題生成手法の解析
- 眼底断層画像の領域抽出・解析手法に関する研究 : 緑内障診断に用いられる視神経構造特徴の自動測定(一般,First Person Visionのための認識・理解)
- 衝突確率を考慮したバッファ配置問題に対する計算機シミュレーションを利用した手法
- 搬送計画問題に対するネットワーク理論を利用したアプローチ
- より大きな値の最近要素を求める定数作業領域アルゴリズム
- 帯状の紙の折りたたみに関する最適化問題
- 正4面体と他の正多面体との共通の辺展開図に関する研究
- グラフ及び領域空間に関する大域丸めの幾何学的性質について
- Spanning Trees Crossing Few Barriers (Algorithm Engineering as a New Paradigm)
- 平面点集合のk巡回路被覆問題: kが定数の場合の多項式時間近似スキーム
- 一般化KaboozleのNP完全性
- 折紙における決定不能問題
- 制約されたメモリ上での2値画像処理の技法
- 眼底断層画像の領域抽出・解析手法に関する研究 : 緑内障診断に用いられる視神経構造特徴の自動測定(一般,First Person Visionのための認識・理解)
- 眼底断層画像の領域抽出・解析手法に関する研究 : 緑内障診断に用いられる視神経構造特徴の自動測定(一般,First Person Visionのための認識・理解)
- 幾何問題に対する定数作業領域アルゴリズム(1)
- パス上のボロノイゲーム
- 帯状の紙の折りたたみに関する最適化問題
- 折紙における決定不能問題
- 幾何問題に対する定数作業領域アルゴリズム(2)
- 2値画像上で連結成分を消去するその場でのアルゴリズム
- 2次元線形計画法に対する決定的な定数ワークスペースアルゴリズム
- 正方行列上に一様に整数を配置する方法の提案とディジタルハーフトーニングへの応用
- 正方行列上に一様に整数を配置する方法の提案とディジタルハーフトーニングへの応用
- 一般化 Kaboozle のNP完全性
- 計算幾何学でいかに論文を書くか(学生/教養のページ)
- Constant-work-space algorithms for geometric problems (1) (コンピュテーション)
- Nearest Larger Neighbors問題に対する効率の良いアルゴリズム (理論計算機科学の深化と応用)
- Constant-Working-Space Algorithms (Computational Geometry and Discrete Mathematics)
- 定数の作業領域だけを用いて任意の角度で画像をスキャンする算法
- 直線上に整数点を一様に生成する算法
- 定数作業領域だけを用いたユークリッド距離変換アルゴリズム
- 定数作業領域だけを用いた連結成分ラベル付けアルゴリズム
- ゾーンダイアグラム : 存在性,一意性,アルゴリズム
- プトレマイオスグラフのラミナー構造とその応用
- k-木のスケールフリー性に関する研究
- k-木のスケールフリー性に関する研究
- UNO は一人でも難しい (計算機科学とアルゴリズムの数理的基礎とその応用)
- 正4面体と正6面体との共通の展開図の構成に関する研究
- 等間隔の折り目を持つ紙の折り畳みの計算量について
- 複数の単位円による点集合の排他的被覆
- Hoffmanパズル解の列挙と一般化に関する研究
- 複数の直方体を折れる共通の展開図に関する研究
- グラフクラスとアルゴリズム
- 複数の直方体を折れる共通の展開図に関する研究
- ゲーム・パズルの計算量を示すための新しい枠組みについて(パズルとゲームの計算理論)
- On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題
- ある投票ゲームのシミュレーション
- 単位正方形上の一意被覆問題に対する近似アルゴリズム
- トロミノ詰込問題の計算複雑さについて
- キャタピラグラフの独立点集合遷移問題に対する多項式時間アルゴリズム
- DS-1-11 Free Flood Filling Gameの計算複雑性について(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- ペンシルパズル「シャカシャカ」の計算複雑さと整数計画モデル
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題