|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Easy to Win, Hard to Master: Optimal Strategies in Parity Games with Costs | | Alexander Weinert
; Martin Zimmermann
; | | Date: |
19 Apr 2016 | | Abstract: | The winning condition of a parity game with costs requires an arbitrary, but
fixed bound on the distance between occurrences of odd colors and the next
occurrence of a larger even one. Such games quantitatively extend parity games
while retaining most of their attractive properties, i.e, determining the
winner is in NP and co-NP and one player has positional winning strategies.
We show that the characteristics of parity games with costs are vastly
different when asking for strategies realizing the minimal such bound: the
solution problem becomes PSPACE-complete and exponential memory is both
necessary in general and always sufficient. Thus, playing parity games with
costs optimally is harder than just winning them. Moreover, we show that the
tradeoff between the memory size and the realized bound is continuous in
general. | | Source: | arXiv, 1604.5543 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER