Logical Approaches to Computational Barriers

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 |