Time: 1:30pm Tuesday, 1st March.
Location: SIT 459
Speaker: Ronald de Haan, TU Wien, Austria
Title: Parameterized Complexity of Problems in the Polynomial Hierarchy
Parameterized complexity provides a theoretical framework that allows for an analysis of the complexity of problems where structure that is present in the input can be taken into account. This provides a way to relativize overly negative hardness results from classical complexity theory. For instance, for many problems that get the classical label “NP-complete”, one can use parameterized complexity to identify efficient algorithms for cases when the input exhibits one of various kinds of structure (these are called fixed-parameter tractable algorithms, or fpt-algorithms). For problems at higher levels of the Polynomial Hierarchy, however, the structure that is required to obtain such fpt-algorithms tends to be very restrictive. Since only few inputs in practical applications show such restrictive structure, fpt-algorithms for these problems are likely to be less useful in practice. Motivated by the impressive performance of SAT solving algorithms (and algorithms for other NP problems), instead of solving problems directly with an fpt-algorithm, one could use fpt-algorithms to encode problem inputs efficiently into an instance of SAT, and subsequently use the SAT algorithm to solve the problem. In this talk, we discuss how to perform a structured parameterized complexity investigation aimed at identifying such fpt-reductions to SAT. We illustrate this by means of various example problems from the domain of artificial intelligence and knowledge representation and reasoning.