ぷよぷよはNP完全 PUYOPUYO is NP-Complete

    • 牟田 秀俊 MUTA Hidetoshi
    • 東京大学大学院情報理工学系研究科 Dept. of Computer Science, Graduate School of Information Science and Technology, the Univ, of Tokyo

抄録

計算量理論の応用法の一つにパズルの計算量を測って難しさを推定するのがある.本研究では, ぷよぷよという同じ色のぷよをくっつけて消すというパズルゲームのオフライン版を3-PARITIONからの還元でNP完全問題であることを示す.

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.

収録刊行物

電子情報通信学会技術研究報告. COMP, コンピュテーション   [収録刊行物詳細]

IEICE technical report. Theoretical foundations of Computing  105(72)  pp.39-44 20050513  [目次]

社団法人電子情報通信学会

参考文献:  7件

参考文献を見るにはログインが必要です。ユーザIDをお持ちでない方は新規登録してください。

被引用文献:  1件

被引用文献を見るにはログインが必要です。ユーザIDをお持ちでない方は新規登録してください。

プレビュー

プレビュー

キーワード

各種コード

  • NII論文ID(NAID)：
    10016436795
  • NII書誌ID(NCID)：
    AN10013152
  • 本文言語コード：
    JPN
  • 資料種別：
    ART
  • ISSN：
    09135685
  • NDL 雑誌記事ID：
    0571405100
  • NDL 雑誌分類：
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL 請求記号：
    Z16-940
  • 収録DB：
    CJP書誌  CJP引用  NDL  NII-ELS 

書き出し