Johannes Schmidt (Université de Marseille), On the Parameterized Complexity of Default Logic and Autoepistemic Logic.
Schedule
- Feb. 3, 2012, 14:30 - 15:00
Abstract
(joint work with A. Meier, M. Thomas, and H. Vollmer).
We investigate the application of Courcelle's Theorem and the logspace version of
Elberfeld et al. in the context of the implication problem for propositional sets of
formulae, the extension existence problem for default logic, as well as the expansion existence problem for autoepistemic logic and obtain fi xed-parameter time
and space efficient algorithms for these problems. On the other hand, we exhibit,
for each of the above problems, families of instances of a very simple structure
that, for a wide range of di fferent parameterizations, do not have efficient fi xed-
parameter algorithms (even in the sense of the large class XPnu), unless P=NP.
(joint work with A. Meier, M. Thomas, and H. Vollmer). We investigate the application of Courcelle's Theorem and the logspace version of Elberfeld et al. in the context of the implication problem for propositional sets of formulae, the extension existence problem for default logic, as well as the expansion existence problem for autoepistemic logic and obtain fi xed-parameter time and space efficient algorithms for these problems. On the other hand, we exhibit, for each of the above problems, families of instances of a very simple structure that, for a wide range of di fferent parameterizations, do not have efficient fi xed- parameter algorithms (even in the sense of the large class XPnu), unless P=NP.