| 講演抄録／キーワード |
| 講演名 |
2005-03-18 16:50
一般化ぷよぷよの連鎖数判定問題
○松金輝久・武永康彦（電通大） |
| 抄録 |
（和） |
計算量に関する研究において、最近ではテトリスのようないわゆる「落ちもの」ゲームの計算量にも興味が集まっている。本研究ではぷよぷよというゲームを取り上げる。一般化ぷよぷよの連鎖数判定問題の NP 完全性を 3-Partition からの帰着によって示す。 |
| （英） |
Recently, complexity of the puzzles like Tetris draw our attention. In this report, we deal with Puyopuyo; it is a computer game well-known in Japan. We prove NP-completeness of maximum chain problem on generalized Puyopuyo by reduction from 3-Partition. |
| キーワード |
（和） |
NP完全性 / 計算量 / パズル / / / / / |
| （英） |
NP-completeness / complexity / puzzle / / / / / |
| 文献情報 |
信学技報, vol. 104, no. 743, COMP2004-85, pp. 95-103, 2005年3月. |
| 資料番号 |
COMP2004-85 |
| 発行日 |
2005-03-11 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|