著者

横田 雅也 築地 立家 北川 智博 諸橋 玄武 岩田 茂樹

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.100, no.402, pp.41-48, 2000-10-20

---

縦横nマスに将棋の盤面を拡張し, その盤面上で詰将棋が与えられる.この詰将棋が詰むかどうかを決定する問題を, 一般化詰将棋問題と呼ぶ.本稿では一般化詰将棋問題が指数時間完全であることを証明する.一般化詰将棋問題の指数時間困難さの証明はG_3を利用する.G_3はすでに指数時間完全であることが知られている問題である(Provably difficult combinatorial games, SIAM J.Comput.8, 1979)

著者

横田 雅也 築地 立家 北川 智博 諸橋 玄武 岩田 茂樹

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 (ISSN:09151915)

巻号頁・発行日

vol.84, no.3, pp.239-246, 2001-03-01

被引用文献数

4

---

縦横nマスの盤面上に与えられた詰将棋で, 攻方が勝てるかどうかを決定する問題を, 一般化詰将棋問題と呼ぶ.本論文では一般化詰将棋問題が指数時間完全であることを証明した.指数時間困難さの証明は, 既に指数時間完全であることが知られている問題G_3(Provably difficult combinatorial games, SIAM J.Comput., vol.8, 1979)から対数領域還元可能であることを示した.

著者

横田 雅也 築地 立家 藤井 愼二 伊藤 大雄

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

電子情報通信学会論文誌 D (ISSN:09151915)

巻号頁・発行日

vol.J84-D1, no.1, pp.58-61, 2001-01-01

---

縦横 N ますに王将を除く各駒が O(N) 枚ずつ配置されている盤面が与えられたとき,詰み手順があるかどうかを判定する問題を一般化詰め将棋問題と呼ぶ.伊藤らはその計算複雑さがNP困難であることを証明した.本論文では盤面とともに手数の上限を単進数で与えたときの一般化詰め将棋問題がPSPACE完全であることを証明する.

著者

横田 雅也 築地 立家 藤井 愼二 伊藤 大雄

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 (ISSN:09151915)

巻号頁・発行日

vol.84, no.1, pp.58-61, 2001-01-01

被引用文献数

1

---

縦横Nますに王将を除く各駒がO(N)枚ずつ配置されている盤面が与えられたとき, 詰み手順があるかどうかを判定する問題を一般化つめ将棋問題と呼ぶ.伊藤らはその計算複雑さがNP困難であることを証明した.本論文では盤面とともに手数の上限を単進数で与えたときの一般化詰め将棋問題がPSPACE完全であることを証明する.