再録 ゲームとクラス

Erik DemaineとMartin Demaineが色々とゲーム系を解析していたり。PushPush is NP-hard in 2Dとか。Solitaire Clobberはソリティア絡みの話。
という訳で倉庫番がPSPACE完全の話はmy Inputs -- 2003.05.03から論文を漁ると吉。
日の目を見なかった問題たち その2 --- パズル好きの貴兄に辛口の一献を ---とその追記も参照。
で、テトリスはNP困難。