TY - GEN
T1 - Games with a uniqueness property
AU - Aida, Shin
AU - Crasmaru, Marcel
AU - Regan, Kenneth
AU - Watanabe, Osamu
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - For two-player games of perfect information such as Chess, we introduce “uniqueness” properties to describe game positions in which a winning strategy (should one exist) is forced to be unique. Depending on how uniqueness is forced, and whether it applies to both players, the uniqueness property is classified as (bi-) weak, (bi-) strong, or global. We prove that any reasonable two-player game G is extendable to a game G∗ with the bi-strong uniqueness property, so that e.g., QBF remains PSPACE-complete under this restriction. For global uniqueness, we introduce a simple game GUPQBF over Boolean formulas with this property, and prove that any reasonable two-player game with global uniqueness is reducible to this game. On the other hand, we also show that GUPQBF resides in “small” counting classes believed properly contained in PSPACE. Our results give a new characterization to some complexity classes such as PSPACE and EXPTIME.
AB - For two-player games of perfect information such as Chess, we introduce “uniqueness” properties to describe game positions in which a winning strategy (should one exist) is forced to be unique. Depending on how uniqueness is forced, and whether it applies to both players, the uniqueness property is classified as (bi-) weak, (bi-) strong, or global. We prove that any reasonable two-player game G is extendable to a game G∗ with the bi-strong uniqueness property, so that e.g., QBF remains PSPACE-complete under this restriction. For global uniqueness, we introduce a simple game GUPQBF over Boolean formulas with this property, and prove that any reasonable two-player game with global uniqueness is reducible to this game. On the other hand, we also show that GUPQBF resides in “small” counting classes believed properly contained in PSPACE. Our results give a new characterization to some complexity classes such as PSPACE and EXPTIME.
UR - https://www.scopus.com/pages/publications/84888910378
U2 - 10.1007/3-540-45841-7_32
DO - 10.1007/3-540-45841-7_32
M3 - Conference contribution
AN - SCOPUS:84888910378
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 396
EP - 407
BT - STACS 2002 - 19th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
A2 - Alt, Helmut
A2 - Ferreira, Afonso
PB - Springer Verlag
T2 - 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002
Y2 - 14 March 2002 through 16 March 2002
ER -