Ronald de Haan
(Vienna University of Technology)
Parameterized Complexity and Hard Logic Problems
February 28th at 17:30, in ILLC Seminar Room (F1.15)
Short version:
In this talk I will give a gentle introduction to parameterized complexity theory, and I will explain how it can be used to improve algorithms for various hard logic problems that come up in computer science and AI.
Longer version:
An important topic in theoretical computer science is the question of what problems can be solved efficiently (in polynomial time) and what problems cannot. An important tool that has been used to shed some light on this question is the notion of NP-completeness. NP-complete problems seem to require exponential running times in general. However, for many NP-complete problems there exist algorithms that perform quite well on large instances occurring in practice. For instance, over the last decade, many algorithms to decide propositional satisfiability (SAT) have been developed that perform extremely well in practice, and routinely solve instances with millions of variables.
Another (more theoretical) way to approach NP-complete problems is to try to "minimize the damage". We seemingly cannot avoid exponential running times, but maybe we can keep the exponential factor somehow small. Parameterized complexity theory essentially tries to do this by distinguishing 'parameters' of the input and restricting the exponential blow-up to these parameters only. Many problems that are intractable in general become (polynomial-time) tractable if the parameter value is small. The theory of parameterized complexity enables a theoretical analysis of algorithms that solve NP-complete problems and that work well in many practical settings.
We will have a look at a recent investigation that combines these two approaches to solving NP-complete problems. We will use the combination of methods from parameterized complexity theory and effective SAT algorithms to try to tackle logic problems that are even 'beyond NP'. Many of these hard problems involve logical formalisms and occur in various areas in Artificial Intelligence and Knowledge Representation & Reasoning.
This talk will be accessible also for those with no particular background in complexity theory. We will keep a high-level view, introduce all involved concepts and methods, and illustrate the theory with examples.