Fixed-Parameter Tractability in Artificial Intelligence and Reasoning (FAIR)

Reasoning is a fundamental task in Computer Science. It is concerned with the derivation of conclusions from some given data or knowledge base. It has many interesting applications especially in Artificial Intelligence such as answer-set programming, reasoning on the web with descriptions logics, belief revision, argumentation, diagnosis, etc. These areas have received vivid research interest in recent years. Strong theoretical foundations have been laid and algorithms have been presented which, at least in theory, solve the most common computational tasks in these areas. However, in practice, it has turned out that the high inherent complexity of most of these tasks is a severe obstacle to the application of these algorithms to problem instances of realistic size. To this date, the high computational complexity of reasoning tasks has not been satisfactorily solved. Over the past decade, Parameterized Complexity Theory has evolved as a promising way of dealing with high complexity. The primary goal of a parameterized complexity analysis for some hard problem is to identify so- called fixed-parameter tractable fragments, i.e., to identify problem parameters that allow for the efficient solution of an intractable problem in case these parameters are small. The tools of Parameterized Complexity Theory have been successfully applied to many areas of Computer Science above all to hard problems in Graph Theory. However, the application of these techniques to hard reasoning problems is still in its infancy. In this project, we want to extend the successful application of parameterized complexity techniques to the area of Artificial Intelligence and Reasoning. In the first place, we will thus initiate a systematic exploration of possible problem parameters and analyse their potential in finding tractable fragments of otherwise intractable reasoning problems. We will then harness the results of the Parameterized Complexity study to develop new efficient algorithms for fragments of hard reasoning problems and to identify directions for the improvement of existing solution methods for these problems.

Reasoning is a fundamental task in Computer Science. It is concerned with the derivation of conclusions from some data or knowledge base. It has many interesting applications especially in Artificial Intelligence. However, many problems in this area have a high complexity, which constitutes a major obstacle to the development of efficient algorithms. The main goal of this project was to apply methods from parameterized complexity in order to get a deeper understanding of these complexities and to develop new algorithms, which work efficiently if the input has certain structural properties. From this, two core themes have been derived for the project plan: 1. Parameterized complexity analyses of computational problems in many areas of AI and Reasoning. 2. Development of new, efficient algorithms for these computational problems based on various algorithmic paradigms. The areas thus visited include many subfields of AI and Reasoning such as Logic Programming, Description Logics, SAT Solving, handling of inconsistent data (due to updates of a knowledge base or merging of conflicting data), Abduction, Planning, and Argumentation. The algorithmic paradigms thus applied include fixed-parameter algorithms, decomposition methods (which often are a special case of fixed-parameter algorithms), reductions from one problem to another (such as reductions to SAT in order to make SAT solvers applicable to other domains), and parallel algorithms using distributed data processing techniques from big data research.