Parameterized Complexity in the Polynomial Hierarchy: Extending Parameterized Complexity Theory to Higher Levels of the Hierarchy

Description

Parameterized Complexity in the Polynomial Hierarchy was co-recipient of the E.W. Beth Dissertation Prize 2017 for outstanding dissertations in the fields of logic, language, and information. This work extends the theory of parameterized complexity to higher levels of the Polynomial Hierarchy (PH). For problems at higher levels of the PH, a promising solving approach is to develop fixed-parameter tractable reductions to SAT, and to subsequently use a SAT solving algorithm to solve the problem. In this dissertation, a theoretical toolbox is developed that can be used to classify in which cases this is possible. The use of this toolbox is illustrated by applying it to analyze a wide range of problems from various areas of computer science and artificial intelligence. Front Matter ....Pages i-xi Introduction (Ronald de Haan)....Pages 1-18 Front Matter ....Pages 19-19 Complexity Theory and Non-determinism (Ronald de Haan)....Pages 21-32 Parameterized Complexity Theory (Ronald de Haan)....Pages 33-41 Front Matter ....Pages 43-43 Fpt-Reducibility to SAT (Ronald de Haan)....Pages 45-69 The Need for a New Completeness Theory (Ronald de Haan)....Pages 71-83 A New Completeness Theory (Ronald de Haan)....Pages 85-135 Fpt-Algorithms with Access to a SAT Oracle (Ronald de Haan)....Pages 137-157 Front Matter ....Pages 159-159 Problems in Knowledge Representation and Reasoning (Ronald de Haan)....Pages 161-179 Model Checking for Temporal Logics (Ronald de Haan)....Pages 181-204 Problems Related to Propositional Satisfiability (Ronald de Haan)....Pages 205-218 Problems in Judgment Aggregation (Ronald de Haan)....Pages 219-250 Planning Problems (Ronald de Haan)....Pages 251-259 Graph Problems (Ronald de Haan)....Pages 261-268 Front Matter ....Pages 269-269 Subexponential-Time Reductions (Ronald de Haan)....Pages 271-283 Non-uniform Parameterized Complexity (Ronald de Haan)....Pages 285-332 Front Matter ....Pages 333-333 Open Problems and Future Research Directions (Ronald de Haan)....Pages 335-347 Conclusion (Ronald de Haan)....Pages 349-353 Back Matter ....Pages 355-398