Rogue脱出判定問題

study

組合せゲーム・パズル ミニプロジェクト 第２回ミニ研究集会
2007/03/16に豊橋技術科学大学だそうで.

Rogue脱出判定問題のPSPACE完全性：新井滋、武永康彦（電気通信大学）
Rogueはキャラクタ端末のディスプレイでよく親しまれていた、コンピュータ上のアドベンチャーゲームである。残り体力のないキャラクターが魔物のいる部屋から脱出できるかという問題が、空腹度のパラメータを設定した場合PSPACE完全であることを示す。

へぇー（ ´・∀・｀）

Rogueの脱出判定問題：武永康彦（電気通信大学）
Rogueはキャラクタ端末のディスプレイでよく親しまれていた、コンピュータ上のアドベンチャーゲームである。残り体力のないキャラクターが魔物のいる部屋から脱出できるかというパズルがデュードニーの「コンピュータレクリエーション」で紹介されているが、その一般化がNP完全であることを証明する。

空腹度が無いとNP完全らしい.