<div class="csl-bib-body">
<div class="csl-entry">Haan, R. de. (2016). <i>Parameterized complexity in the polynomial hierarchy</i> [Dissertation, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2016.40633</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2016.40633
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/7961
-
dc.description
Zusammenfassung in deutscher Sprache
-
dc.description.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. 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.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
parameterized complexity
en
dc.subject
Polynomial Hierarchy
en
dc.subject
fpt-reductions
en
dc.subject
SAT encodings
en
dc.title
Parameterized complexity in the polynomial hierarchy
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2016.40633
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Ronald de Haan
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen