ぷよぷよは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   [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:  2

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 :
    7355717
  • NDL Source Classification :
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No. :
    Z16-940
  • Databases :
    CJP  CJPref  NDL  NII-ELS