LA 2000: Papers on Internetはじめに LAの会誌31号で、私は勝手にはじめた『日の目を見なかった問題たち』と 銘打ったシリーズ物の第2回目をやらせてもらいました。そこでとりあげたのは 『倉庫番』という一人ゲームでした。そしてこの倉庫番を一般化し、 n×nの盤面に拡張したゲームを考え、このゲームの複雑さは PSPACE完全に違いないと書いてしまいました。 そして最後に もし『倉庫番がXX完全である』ことが証明できたらどうかご一報下さい。 と呼び掛けておきました。本稿はこのお話の続編です。本稿の結論を最初に書 いてしまうと「この問題はやっぱりPSPACE完全でした」ということです。 なんとすでにFUN '98という 国際会議で Culberson 氏によって発表された、 既知の結果でした[Cul98]。 私と一緒に悩んで下さった方、一歩出遅れました。ごめんなさい。 ちなみに Culberson 氏の PSPACE 完全性
Engadget | Technology News & Reviews
