著者

水野 秀一 田中 哲朗

雑誌

情報処理学会研究報告ゲーム情報学(GI)

巻号頁・発行日

vol.2008, no.28(2008-GI-019), pp.53-59, 2008-03-12

---

I.Q はよく知られたパズルゲームであるが,その計算量の議論はこれまで行われてこなかった.本論文では,I.Q のクリアにおいて重要な概念であるターン数に着目し,決められたターンにすべてのキューブを捕獲することができるかどうかというターン数判定問題が NP 完全であることを証明した.