Parameterized complexity in the polynomial hierarchy

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.