ぷよぷよはNP完全 牟田 秀俊 社団法人電子情報通信学会 電子情報通信学会技術研究報告. COMP, コンピュテーション 09135685 105 72 39 44 2005-05-13 計算量理論の応用法の一つにパズルの計算量を測って難しさを推定するのがある.本研究では, ぷよぷよという同じ色のぷよをくっつけて消すというパズルゲームのオフライン版を3-PARITIONからの還元でNP完全問題であることを示す. 2005-05-13 10016436795 AN10013152 7355717 JPN CJP CJPref NDL NII-ELS 1 7 2 PUYOPUYO is NP-Complete MUTA Hidetoshi The Institute of Electronics, Information and Communication Engineers IEICE technical report. Theoretical foundations of Computing In this research, we analyze the complexity of the offline version of Puyopuyo. Puyopuyo is the game in which the player make same colored puyos connected and cleared. 牟田 秀俊 MUTA Hidetoshi 東京大学大学院情報理工学系研究科 Dept. of Computer Science, Graduate School of Information Science and Technology, the Univ, of Tokyo