ぷよぷよはNP完全  [in Japanese] PUYOPUYO is NP-Complete  [in Japanese]

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

Abstract

計算量理論の応用法の一つにパズルの計算量を測って難しさを推定するのがある.本研究では, ぷよぷよという同じ色のぷよをくっつけて消すというパズルゲームのオフライン版を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.

Journal

IEICE technical report. Theoretical foundations of Computing   [Journal Detail]

電子情報通信学会技術研究報告. COMP, コンピュテーション  105(72)  pp.39-44 20050513  [Index]

The Institute of Electronics, Information and Communication Engineers

References:  7

You must have a user ID to see the references.If you already have a user ID, please click "Login" to access the info.New users can click "Sign Up" to register for an user ID.

Cited by:  1

You must have a user ID to see the cited references.If you already have a user ID, please click "Login" to access the info.New users can click "Sign Up" to register for an user ID.

Preview

Preview

Codes

  • NII Article ID (NAID)：
    10016436795
  • NII NACSIS-CAT ID (NCID)：
    AN10013152
  • Text Lang：
    JPN
  • Article Type：
    Journal Article
  • ISSN：
    09135685
  • NDL Article ID：
    0571405100
  • NDL Source Classification：
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.：
    Z16-940
  • Databases：
    CJP書誌  CJP引用  NDL  NII-ELS 

Export