講演抄録/キーワード |
講演名 |
2022-03-06 10:30
一般化詰中将棋問題の指数時間完全性 ○上嶋章宏・木場裕矢・大森潤一・佐藤正彬(阪電通大) COMP2021-32 |
抄録 |
(和) |
本将棋に対する詰将棋と同様に,古将棋の一種である中将棋に対し詰中将棋を定義し,盤面を$n times n$に一般化したとき,与えられた局面から先手が勝てるか否かを決定する問題が指数時間完全であることを示す.本稿では,既知の指数時間完全問題である$G_4$ゲーム(Provably difficult combinatorial games SIAM J. Comput., vol. 8, 1979)から対数領域還元可能であることを証明する. |
(英) |
We consider the `Tsume-ChuShogi' that restricted chushogi such that at every turn, the attack-side player (the first player) must check the defence-side Gyoku (King), like Tsume-Shogi for Shogi. The computational complexity of a generalized Tsume-Chushogi by spreading the boards into $n times n$ is investigated. We show that the problem to determine whether the attack-side player can give checkmate the game is EXPTIME-complete by using a log-space reduction from $G_4$ game, which is already known EXPTIME-complete (Provably difficult combinatorial games, SIAM J. Comput., vol. 8, 1979). |
キーワード |
(和) |
計算複雑さの理論 / 中将棋 / 一般化詰中将棋 / 指数時間完全 / / / / |
(英) |
computational complexity theory / Chu-Shogi / Generalized Tsume-Chushogi / EXPTIME-completeness / / / / |
文献情報 |
信学技報, vol. 121, no. 407, COMP2021-32, pp. 8-15, 2022年3月. |
資料番号 |
COMP2021-32 |
発行日 |
2022-02-27 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2021-32 |