Aarhus University Seal / Aarhus Universitets segl

Winning Concurrent Reachability Games Requires Doubly-Exponential Patience

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Department of Computer Science
We exhibit a deterministic concurrent reachability game PURGATORYn with n non-terminal positions and a binary choice for both players in every position so that any positional strategy for Player 1 achieving the value of the game within given isin < 1/2 must use non-zero behavior probabilities that are less than (isin2/(1 - isin))2n-2 . Also, even to achieve the value within say 1 - 2-n/2, doubly exponentially small behavior probabilities in the number of positions must be used. This behavior is close to worst case: We show that for any such game and 0 < isin < 1/2, there is an isin-optimal strategy with all non-zero behavior probabilities being 20(n) at least isin2O(n). As a corollary to our results, we conclude that any (deterministic or nondeterministic) algorithm that given a concurrent reachability game explicitly manipulates isin-optimal strategies for Player 1 represented in several standard ways (e.g., with binary representation of probabilities or as the uniform distribution over a multiset) must use at least exponential space in the worst case.
Original languageEnglish
JournalSymposium on Logic in Computer Science
Pages (from-to)332-341
Number of pages10
ISSN1043-6871
DOIs
Publication statusPublished - 2009
EventAnnual IEEE Symposium on Logic in Computer Science. LICS'09 - Los Angeles, United States
Duration: 11 Aug 200914 Aug 2009
Conference number: 24

Conference

ConferenceAnnual IEEE Symposium on Logic in Computer Science. LICS'09
Number24
CountryUnited States
CityLos Angeles
Period11/08/200914/08/2009

See relations at Aarhus University Citationformats

ID: 17930828