On Fixed-Parameter Complexity of Infinite Games

• We investigate and classify fixed parameter complexity of several infinite duration games, including Rabin, Streett, Muller, parity, mean payoff, and simple stochastic, using different natural parameterizations.Most known fixed parameter intractable games are PSPACE- or EXP-complete classically, AW[*] or XP-hard parametrically, and are all finite duration games. In contrast, the games we consider are infinite duration, solvable in positional or finite memory strategies, and belong to "lower" complexity classes, like NP and/or coNP. However, the best known algorithms they possess are of complexity nf(k), i.e., XP is the only upper bound, with no known parametric lower bounds.We demonstrate that under different parameterizations these games may have different or equivalent FPT-statuses, and present several tractable and intractable cases.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

Publikations- och innehållstyp

vet (ämneskategori)

rap (ämneskategori)