Faculdade

Eventos

Fixed-parameter tractable reductions to SAT by Ronald de Haan (Vienna University of Technology)

 

Title: Fixed-parameter tractable reductions to SAT
By: Ronald de Haan (Vienna University of Technology)
Abstract:
Modern propositional satisfiability (SAT) solvers perform extremely well in many practical settings and can be used as an efficient back-end for solving NP-complete problems. However, many fundamental problems in Knowledge Representation and Reasoning are located at the second level of the Polynomial Hierarchy (PH) or even higher, and hence for these problems polynomial-time transformations to SAT are not possible, unless the PH collapses. Recent research shows that in certain cases one can break through these complexity barriers by fixed-parameter tractable (fpt) reductions which exploit structural aspects of problem instances in terms of problem parameters.
We develop a general theoretical framework that supports the classification of parameterized problems on whether they admit such an fpt-reduction to SAT or not. We base this framework on its application to concrete reasoning problems from various domains. We develop several parameterized complexity classes to provide evidence that in certain cases such fpt-reductions to SAT are not possible. Moreover, we relate these new classes to existing parameterized complexity classes. Additionally, for problems for which there exists a Turing fpt-reduction to SAT, we develop techniques to provide lower bounds on the number of calls to a SAT solver needed to solve these problems.
Short-bio:
Ronald de Haan is a PhD student in the Knowledge-Based Systems Group at the Vienna University of Technology. He is a student in the European PhD Program in Computational Logic (EPCL). His research focuses on parameterized complexity theory and reasoning problems located at higher levels of the Polynomial Hierarchy. He has a wide range of research interests, including complexity theory and computational logic. He is a graduate of the European Master's Program in Computational Logic (EMCL), where he received several awards for his master's thesis. He attended Utrecht University for his undergraduate education, and holds bachelor's degrees in Cognitive Artificial Intelligence and Linguistics.