Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
On the complexity of computing winning strategies for finite poset games

Author(s): Michael Soltys and Craig Wilson
Slot: Array, 11:20-11:40, col. 5


We give a simple polytime reduction from poset games into
the game of geography. This is a direct way of showing that it can be
decided in PSPACE whether in a given configuration of a poset game,
the next player has a winning strategy. We also attempt the reverse
reduction, and give some weak partial results; the question whether
deciding poset games is PSPACE-complete remains open. We also
formalize the proof of the existence of a winning strategy for poset games
(these are poset games with a supremum) in Skelley's theory W_1^1 for
PSPACE reasoning, and hence obtain an alternative way of extracting
winning strategies that can be computed in PSPACE. We hope that a
program consisting in formalizing proofs of existence of winning
strategies in weaker and weaker fragments of Bounded Arithmetic can yield
better algorithms (i.e., algorithms of lower complexity) for computing
the winning strategies.

websites: Arnold Beckmann 2008-05-19