Complexity analysis of voting systems, exact and critical problems, and symmetric alternation

点击翻译按钮获取中文摘要

In diesem Projekt werden komplexitätstheoretische Untersuchungen zu Wahlsystemen, exakten Optimierungsproblemen, kritischen Problemen und zur symmetrischen Alternation durchgeführt. Wahlsysteme sind Regeln, mit denen aus einer Gruppe von Kandidaten die Sieger einer Abstimmung bestimmt werden können. Neben der Frage der Fairness einer Wahl, die in der Politikwissenschaft untersucht wird, treten in der Informatik zunehmend algorithmische Fragen nach der effizienten Durchführbarkeit von Wahlen und ihrer Manipulierbarkeit in den Vordergrund. Beispielsweise sind vom Kemeny-Wahlsystem inspirierte Aggregationssysteme nützlich, um die Manipulation des Website-Rankings von Suchmaschinen und "Spamming" zu verhindern. In diesem Projekt werden insbesondere das Gewinner-, Ranking- und Manipulationsproblem verschiedener Wahlsysteme untersucht und komplexitätstheoretisch klassifiziert. Weiterhin werden Vollständigkeitsresultate von exakten Optimierungsproblemen und kritischen Problemen in den Stufen der booleschen Hierarchie über NP angestrebt. Schließlich soll der vor kurzem eingeführte Begriff der symmetrischen Alternation im Hinblick auf die Polynomialzeit-Hierarchie und die interaktiven Beweissysteme untersucht werden. Das aktuelle Forschungsgebiet der interaktiven Beweissysteme ist sowohl in der Komplexitätstheorie als auch in der Kryptographie von großer Bedeutung.