I.Q Intelligent Qube の NP 完全性の証明

• Item type: SIG Technical Reports(1)
• 公開日: 2008-03-12
• タイトル: I.Q Intelligent Qube の NP 完全性の証明
• タイトル / 言語: en
• タイトル: NP-completeness of I.Q Intelligent Qube
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学大学院総合文化研究科広域科学専攻
• 著者所属: 東京大学情報基盤センター
• 著者所属(英): en
• 著者所属(英): The University of Tokyo Graduate School of Arts and Science
• 著者所属(英): en
• 著者所属(英): Information Technology Center, The University of Tokyo
• 著者名: 水野, 秀一; 田中, 哲朗
• 著者名(英): Shuichi, Mizuno; Tetsuro, Tanaka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: I.Q はよく知られたパズルゲームであるが，その計算量の議論はこれまで行われてこなかった．本論文では，I.Q のクリアにおいて重要な概念であるターン数に着目し，決められたターンにすべてのキューブを捕獲することができるかどうかというターン数判定問題が ＮＰ 完全であることを証明した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Up to now, the computational complexity of I.Q has not been discussed though it is a puzzle game known well. In this paper, wo proofed NP-completeness of the turn number decision problem which is whether to catch all cube in given turns.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11362144
• 書誌情報: 情報処理学会研究報告ゲーム情報学（GI）; 巻 2008, 号 28(2008-GI-019), p. 53-59, 発行日 2008-03-12
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会