Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs [Elektronische Ressource] / Oliver Friedmann. Betreuer: Martin Lange

Doctoral ThesisExponential Lower Bounds for Solving InfinitaryPayoff Games and Linear ProgramsOliver FriedmannChair of Theoretical Computer ScienceDepartment of ScienceLudwig-Maximilians-University MunichFirst advisor: Prof. Dr. Martin Hofmann, University of MunichSecond advisor: Prof. Dr. Martin Lange, University of KasselExternal examiner: Prof. Dr. Erich Grädel, RWTH AachenSubmitted: April 4th, 2011Defended: July 15th, 2011iAbstractParity games form an intriguing family of infinitary payoff games whose solutionis equivalent to the solution of important problems in automatic verification andautomata theory. They also form a very natural subclass of mean and discountedpayoff games, which in turn are very natural subclasses of turn-based stochasticpayoff games. From a theoretical point of view, solving these games is one of the fewproblems that belong to the complexity classNP\coNP, and even more interestingly,solving has been shown to belong toUP\coUP, and also toPLS. It is a major openproblem whether these game families can be solved in deterministic polynomialtime.Policy iteration is one of the most important algorithmic schemes for solvinginfinitary payoff games. It is parameterized by an improvement rule that determineshow to proceed in the iteration from one policy to the next. It is a major open problemwhether there is an improvement rule that results in a polynomial time algorithm forsolving one of the considered game classes.