(funded by the Austrian Science Fund (FWF) under grant P25518)
The project has officially started on 2013-05-01 and will have a duration of three years.Top
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 - such as answer-set programming, reasoning on the web with description 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 intractable problems 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 analyze 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.Top