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

Search this Article

Author(s)

    • 牟田 秀俊 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   [List of Volumes]

    IEICE technical report. Theoretical foundations of Computing 105(72), 39-44, 2005-05-13  [Table of Contents]

    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:  3

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.

Codes

  • NII Article ID (NAID)
    10016436795
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    09135685
  • NDL Article ID
    7355717
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  CJPref  NDL  NII-ELS 
Page Top