ぷよぷよは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, コンピュテーション   [巻号一覧]

    電子情報通信学会技術研究報告. COMP, コンピュテーション 105(72), 39-44, 2005-05-13  [この号の目次]

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

参考文献:  7件

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

被引用文献:  3件

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

キーワード

各種コード

  • NII論文ID(NAID)
    10016436795
  • NII書誌ID(NCID)
    AN10013152
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    09135685
  • NDL 記事登録ID
    7355717
  • NDL 雑誌分類
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL 請求記号
    Z16-940
  • データ提供元
    CJP書誌  CJP引用  NDL  NII-ELS 
ページトップへ