[Back]

St. Rümmele:
"The Parameterized Complexity of Nonmonotonic Reasoning";
Supervisor, Reviewer: F. Scarcello, G. Brewka; Institut für Informationssysteme, 2012; oral examination: 2012-09-13.

In our daily life we encounter situations where already drawn conclusions can turn out to be invalid because new information becomes available which we did not know before. Human reasoning is not
only capable of dealing with such nonmonotonic situations, but also is this kind of reasoning permanently performed by humans. Hence, it is no surprise that lots of research in artificial intelligence (AI)
and knowledge representation (KR) is conducted in order to study so-called nonmonotonic reasoning formalisms.
Examples of such formalisms are belief revision, answer-set programming, and (propositional) abduction. A big obstacle that limits the practical applicability of computational nonmonotonic reasoning is the high complexity of these tasks. A promising approach to dealing with high computational complexity is to study what kind of properties those problem instances have that can be solved efficiently. Such tractable fragments are not restricted to syntactical limitations, such as Horn formulas instead of
general propositional formulas. We are more interested in structural fragments since they often tell us something about the (hidden) structure of certain problem instances. The framework within which the search for such structural fragments can be conducted is called parameterized complexity theory. Thereby a multivariate complexity analysis of the problem is performed, where the input size is just one dimension. The other dimensions that are studied are called parameters. To overcome the high complexity of nonmonotonic reasoning problems, we seek parameters or combinations
of parameters such that the computational hardness of the problem can be confined in them. This means that if we consider fragments of problem instances with sufficiently small parameter values, we obtain new tractable fragments. In this thesis we will study the three above mentioned nonmonotonic reasoning formalisms. We initiate the research of parameterized complexity of belief revision as well as propositional abduction. Furthermore, we significantly advance the state-of-the-art of parameterized complexity of answer-set
programming.