d.y.d. Bowling21:11 07/02/26 俺定義で書けたら via この辺。 それをネタ元にして一人用パズルゲームが作れたらNP完全ぽい。 二人用対戦ゲームが作れたらPSPACE完全ぽい、というのを時々聞きます。 NP完全の一番基本的な問題が SAT: bool型変数 x1 ～ xn を and と or と not で組み合わせた式があります。 さあ、あなたは、変数 x1 ～ xn の値をうまく決めて式全体の値を true にすることができますか？？ という答えを見つけましょう系なのに対して、PSPACE完全の一番基本的な問題が QBF: bool型変数 x1 ～ xn を and と or と not で組み合わせた式があります。 x1 をうまく決めて、「例えx2 がtrueでもfalseでも、そこですかさず x3 をうまく決めたら、 x4 がtrueになってもfalseになっても (以下繰り返し
Game complexity - Wikipedia
