Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

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

Edit abstract data

Author(s): Michael Soltys and Craig Wilson
Slot: Thu, 11:20-11:40, Room 19 (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 Valid HTML 4.01! Valid CSS!