Copy
Takayuki YATO, Takahiro SETA, Tsuyoshi ITO, "Finding Yozume of Generalized Tsume-Shogi is Exptime-Complete" in IEICE TRANSACTIONS on Fundamentals,
vol. E88-A, no. 5, pp. 1249-1257, May 2005, doi: 10.1093/ietfec/e88-a.5.1249.
Abstract: Generalized Tsume-Shogi (GTS) is Tsume-Shogi on the board of size n n for arbitrary n. The problem to decide the existence of a winning sequence of moves (where the attacker must always check) on an instance of GTS was proved to be exptime-complete by Yokota et al. (2000). This paper considers the complexity of yozume problem of GTS, which is, roughly speaking, the problem whether a given position of GTS has a winning sequence other than given sequences (though the actual rule of yozume is more complicated). The detection of yozume is an important issue in designing Tsume-Shogi problems, since the modern designing rule strongly prohibits it. We define a function problem of GTS appropriately to formulate yozume problem as its Another Solution Problem (ASP; the problem to decide the existence of solutions other than given ones). Moreover, we extend the existing framework for investigating ASPs so that it can be applied to exptime-complete problems. In particular, since the decision of correctness of given winning sequences is not easy, we establish a framework to treat ASP of function problems with promises. On the basis of these results, we prove that the decision version of yozume problem of GTS is exptime-complete as a promise problem using the existing reduction which was constructed by Yokota et al. to prove the exptime-completeness of GTS.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.5.1249/_p
Copy
@ARTICLE{e88-a_5_1249,
author={Takayuki YATO, Takahiro SETA, Tsuyoshi ITO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Finding Yozume of Generalized Tsume-Shogi is Exptime-Complete},
year={2005},
volume={E88-A},
number={5},
pages={1249-1257},
abstract={Generalized Tsume-Shogi (GTS) is Tsume-Shogi on the board of size n n for arbitrary n. The problem to decide the existence of a winning sequence of moves (where the attacker must always check) on an instance of GTS was proved to be exptime-complete by Yokota et al. (2000). This paper considers the complexity of yozume problem of GTS, which is, roughly speaking, the problem whether a given position of GTS has a winning sequence other than given sequences (though the actual rule of yozume is more complicated). The detection of yozume is an important issue in designing Tsume-Shogi problems, since the modern designing rule strongly prohibits it. We define a function problem of GTS appropriately to formulate yozume problem as its Another Solution Problem (ASP; the problem to decide the existence of solutions other than given ones). Moreover, we extend the existing framework for investigating ASPs so that it can be applied to exptime-complete problems. In particular, since the decision of correctness of given winning sequences is not easy, we establish a framework to treat ASP of function problems with promises. On the basis of these results, we prove that the decision version of yozume problem of GTS is exptime-complete as a promise problem using the existing reduction which was constructed by Yokota et al. to prove the exptime-completeness of GTS.},
keywords={},
doi={10.1093/ietfec/e88-a.5.1249},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Finding Yozume of Generalized Tsume-Shogi is Exptime-Complete
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1249
EP - 1257
AU - Takayuki YATO
AU - Takahiro SETA
AU - Tsuyoshi ITO
PY - 2005
DO - 10.1093/ietfec/e88-a.5.1249
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2005
AB - Generalized Tsume-Shogi (GTS) is Tsume-Shogi on the board of size n n for arbitrary n. The problem to decide the existence of a winning sequence of moves (where the attacker must always check) on an instance of GTS was proved to be exptime-complete by Yokota et al. (2000). This paper considers the complexity of yozume problem of GTS, which is, roughly speaking, the problem whether a given position of GTS has a winning sequence other than given sequences (though the actual rule of yozume is more complicated). The detection of yozume is an important issue in designing Tsume-Shogi problems, since the modern designing rule strongly prohibits it. We define a function problem of GTS appropriately to formulate yozume problem as its Another Solution Problem (ASP; the problem to decide the existence of solutions other than given ones). Moreover, we extend the existing framework for investigating ASPs so that it can be applied to exptime-complete problems. In particular, since the decision of correctness of given winning sequences is not easy, we establish a framework to treat ASP of function problems with promises. On the basis of these results, we prove that the decision version of yozume problem of GTS is exptime-complete as a promise problem using the existing reduction which was constructed by Yokota et al. to prove the exptime-completeness of GTS.
ER -
English
