The Parameterized Complexity of Reasoning Problems

Reasoning, to derive conclusions from facts, is a fundamental task in Artificial Intelligence that arises in a wide range of applications from Robotics to Expert Systems. Different applications require different forms of reasoning such as Nonmonotonic Reasoning (e.g., reasoning under the presence of default as- sumptions), Constraint-Based Reasoning (reasoning with forbidden configurations), and Bayesian Reasoning (reasoning with uncertain data). All these forms of reasoning give rise to computational problems that can be solved algorithmically. The efficiency of algorithms has a direct impact on applications; for example, improved algorithms for Bayesian inference yield more accurate computer assisted medical diagnosis.

The aim of this project is to devise new efficient algorithms for reasoning problems and to gain new theoretical insights into the question of what makes a reasoning problem hard, and what makes it easy. We study reasoning problems within the framework of Parameterized Complexity, a new and rapidly emerging field of Algorithms and Complexity. Parameterized Complexity takes structural aspects of problem instances into account which are most significant for empirically observed problem-hardness. Most of the considered reasoning problems are intractable in general, but the real-world context of their origin provides structural information that can be made accessible to algorithms in form of parameters. This makes Parameterized Complexity an ideal setting for the analysis and efficient solution of these problems that we want to explore.

Two inputs for a reasoning problem: random (left) and realistic (right).

An Illustration: the picture to the right shows the visualizations of two inputs for a reasoning problem. The input to the left is a random input. The input to the right is a real-world input (from multiplier verification). Both inputs have approximately the same size in bits, however, evidently the real-world instance is somehow “structured”, whereas the random instance is not. The parameterized complexity approach allows to utilize this kind of structure to solve the problem efficiently.

Project Record

Project Title: The Parameterized Complexity of Reasoning Problems
Principle Investigator: Stefan Szeider
Funding Organization: European Research Council (ERC)
Project Type: ERC Starting Independent Researcher Grant
Project Volume: Eur 1.4 Mio
Project Duration: Jan 2010 - Dec 2014
Host Institution: Vienna University of Technology

Project team

• Simone Bova
• Johannes Fichte
• Robert Ganian
• Ronald de Haan
• Eva Nedoma
• Friedrich Slivovsky
• Stefan Szeider, project leader
• Yue Chen
• Serge GaspersUniversity of NSW and NICTA, Australia)
• Sebastian Ordyniak

[

de Haan, Fichte, Slivovsky, Gaspers, Ordyniak, Szeider, Bova, Ganian (from left to right)