[Back]


Doctor's Theses (authored and supervised):

R. de Haan:
"Parameterized Complexity in the Polynomial Hierarchy";
Supervisor, Reviewer: S. Szeider, M. Grohe, R. Pichler; Institut für Computergraphik und Algorithmen, 2016; oral examination: 2016-11-08.



English abstract:
We investigate how parameterized complexity theory can be used effectively to analyze
problems at higher levels of the Polynomial Hierarchy (PH). A key part of this investigation
is the development of new parameterized complexity classes that lie between the first
and second level of the PH.
The framework of parameterized complexity has been used productively over the last two
decades to yield a detailed picture of the computational complexity of problems in NP. In
parameterized complexity, the inherent difficulty of problems is measured with respect to
multiple parameters of the input, rather than just the input size in bits. However, many
relevant problems that come up in artificial intelligence and other branches of computer
science are located at higher levels of the PH. The theoretical tools developed in the
literature are of limited use in the parameterized complexity analysis of such problems.
This is largely due to the fact that these tools are built exclusively around the notion of
fixed-parameter tractability. To adequately study the complexity of problems at higher
levels of the PH, additional theory is needed that incorporates other, more permissive
notions of tractability. These tractability notions are based on fixed-parameter tractable
encodings into problems (in NP) for which optimized solving algorithms are available
that work extremely well in many practical settings.
We develop a new theoretical toolbox that enables a more satisfactory parameterized
complexity analysis of problems at higher levels of the PH. Moreover, we use this new
machinery to initiate an extensive investigation of the parameterized complexity of many
natural problems from a variety of domains.
We achieve these results by means of a theoretical, mathematical study. We develop a
range of new parameterized complexity classes that lie between the first and second level
of the PH, and we relate these to known classes. These complexity classes can be used to
establish both positive and negative results. Additionally, we substantiate the developed
theory by showing that many natural problems from different areas are complete for
these new classes.
The results in this thesis can immediately be used in future research to better identify
settings where the technique of employing fixed-parameter tractable encodings into NP
problems has the potential to lead to practically efficient solving algorithms. Moreover,
our results open up a range of interesting and relevant questions for future theoretical
research.

German abstract:
In dieser Arbeit wird untersucht, wie man die Theorie der parametrisierten Komplexität
benutzen kann, um Probleme auf höheren Ebenen der Polynomialzeithierarchie (PH)
zu analysieren. Eine zentrale Rolle in dieser Untersuchung spielt die Entwicklung neuer
parametrisierter Komplexitätsklassen zwischen der ersten und der zweiten Ebene der PH.
Das Paradigma der parametrisierten Komplexität hat sich in den vergangenen zwei Jahrzehnten
als nützlich erwiesen, um ein detailliertes Bild von der Berechnungskomplexität
von Problemen in NP zu erhalten. In diesem Paradigma wertet man die Berechnungskomplexität
von Problemen anhand mehrerer Parameter der Eingabe, anstatt nur der
Eingabegröße in Bits. Viele relevante Probleme, die im Bereich der Künstlichen Intelligenz
und in anderen Bereichen der Informatik auftreten, befinden sich dennoch auf höheren
Ebenen der PH. Die bisher verwendeten theoretischen Werkzeuge der parametrisierten
Komplexität sind für die rigorose Analyse solcher Probleme nur sehr eingeschränkt anwendtbar.
Ein wichtiger Grund dafür ist die Tatsache, dass diese Werkzeuge ausschließlich
um die Idee der Fest-Parameter-Handhabbarkeit (fixed-parameter tractability) herum
entwickelt worden sind. Um die Komplexität von Problemen auf höheren Ebenen der PH
umfassend untersuchen zu können, ist ein neuer theoretischen Rahmen erforderlich,
der mächtigere Konzepte der Berechenbarkeit miteinbezieht. Solche Konzepte basieren
auf fest-Parameter-handhabbaren Reduktionen auf Probleme (in NP), für die optimierte
Lösungsalgorithmen existieren, die in vielen praktischen Situationen sehr effizient
funktionieren.
Wir entwickeln neue theoretischeWerkzeuge, die eine rigorose parametrisierte Komplexitätsanalyse
der Probleme auf höheren Ebenen der PH ermöglichen. Zudem verwenden wir
dieses neu entwickelte Instrumentarium um eine rigorose Untersuchung vieler natürlichen
Probleme aus verschiedenen Bereichen zu initiieren.
Diese Ergebnisse erreichen wir mittels einer theoretischen/mathematischen Studie. Wir
entwickeln eine breite Palette an neuen parametrisierten Komplexitätsklassen, die sich
zwischen der ersten und der zweiten Ebene der PH befinden, und wir untersuchen
das Verhältnis dieser neuen Klassen untereinander, und zu bisher verwendeten Klassen.
Die neuen Komplexitätsklassen können dafür benutzt werden um sowohl positive als
auch negative Komplexitätsergebnisse zu erlangen. Außerdem untermauern wir die neu
entwickelte Theorie, indem wir zeigen, dass viele natürliche Probleme aus verschiedenen
Bereichen der Informatik für diese neuen Komplexitätsklassen vollständig sind.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/publik_254596.pdf


Created from the Publication Database of the Vienna University of Technology.