ゲームと困難性
前置き
全て頭に一般化が付きます. 色々結果はありますが, 問題の定式化によって当然難しさが変わりますのでご注意を. 定義は元論文を見て確認してください.
2人ゲーム
1人ゲーム
- 一般化詰め将棋
- EXPTIME完全 (横田, 築地, 北川, 諸橋, 岩田 2001)
- 倉庫番
- PSPACE完全 (Cullberson 1998)
- Rogue脱出判定問題
- NP完全 (武永 2005)
- Rogue脱出判定問題 (空腹度付き)
- PSPACE完全 (新井, 武永 2007)
- //www.planarity.net/">www.planarity.net:NP困難など (Okamoto, Goaoc, Kratochvil, Shin, Wolff 2007?)
- フリーセル
- NP完全 (Helmert 2003) (各スートに付き1-nの番号のカードということで.)
- さめがめ
- NP完全 (Biedl, Demain, Demain, Fleischer, Jacobsen, and Ian Munro 2002)
- テトリス
- NP完全 (近似版も難しい) (Breukelaar, Demaine, Hohenberger, Hoogeboom, Kosters, and Liben-Nowell 2004)
- ぷよぷよ
- NP完全
- Hi-Q
- NP完全 (上原, 岩田 1990)
- 箱入娘
- PSPACE完全 (Hearn and Demaine 2002)
- 折り紙
- NP困難 (問題の定式化が色々ある)
- 飛び出す絵本
- 拡げるのも畳むのもNP困難 (上原, 寺本 2005)
ペンシルパズル系
八登さんが纏めているのでそれらをリストにしてみた. 一部の問題ではASP完全性が示されており, 解の数を数えることが#P完全になっているらしい. うわぁ(;´Д｀)
- お絵描きロジック
- NP完全 (上田, 永尾 1996)
- ぬりかべ
- NP完全 (McPhail 2003)
- 美術館
- NP完全 (McPhail 2003)
- バトルシップ
- NP完全 (Sevenster 2004他)
- マインスイーパー
- NP完全 (初期盤面 (既知の爆弾の場所) の指定あり) (Kaye 2000?)
- ボンバーパズル (マインスイーパーの部分問題)
- NP完全
- カックロ
- NP完全 (瀬田 2002)
- ナンバープレース (数独)
- NP完全 (八登 2003)
- スケルトン
- NP完全
- スリザーリンク
- NP完全 (八登 2003)
- ナンバーリンク
- NP完全 (Kramer and van Leeuwen 1982, Richards 1984)
- ましゅ
- NP完全 (Friedman 2002) (このパズル矢野龍王考案か...)
- バッグ
- NP完全 (Friedman 2002)
- 天体ショー
- NP完全 (Friedman 2002)
- フィルオミノ
- NP完全 (八登 2003)
- 覆面算
- NP完全 (Eppstein 1987, de Bondt 2004) (注:10進数だと線形時間)
