読者です 読者をやめる 読者になる 読者になる

ゲームと困難性

前置き

全て頭に一般化が付きます. 色々結果はありますが, 問題の定式化によって当然難しさが変わりますのでご注意を. 定義は元論文を見て確認してください.

2人ゲーム

オセロ
PSPACE完全 (岩田, 笠井 1994)
将棋
EXPTIME完全 (安達, 亀川, 岩田 1987)
囲碁
EXPTIME完全
チェッカー
EXPTIME完全 (Robson 1984)
チェス
EXPTIME完全
一般化しりとり
PSPACE完全
マスターマインド
NP完全 (de Bondt 2004, Stuckman and Zhang 2005)
一般化アマゾン
PSPACE完全 (清見, 宇野 2005)
シャノンのスイッチングゲーム
PSPACE完全

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進数だと線形時間)