The Parameterized Complexity of Abduction

Authors

  • Michael Fellows Charles Darwin University
  • Andreas Pfandler Vienna University of Technology
  • Frances Rosamond Charles Darwin University
  • Stefan Rümmele Vienna University of Technology

DOI:

https://doi.org/10.1609/aaai.v26i1.8224

Keywords:

Abduction, Complexity Theory, Parameterized Complexity Theory, Kernelization

Abstract

Abduction belongs to the most fundamental reasoning methods. It is a method for reverse inference, this means one is interested in explaining observed behavior by finding appropriate causes. We study logic-based abduction, where knowledge is represented by propositional formulas. The computational complexity of this problem is highly intractable in many interesting settings. In this work we therefore present an extensive parameterized complexity analysis of abduction within various fragments of propositional logic together with (combinations of) natural parameters.

Downloads

Published

2021-09-20

How to Cite

Fellows, M., Pfandler, A., Rosamond, F., & Rümmele, S. (2021). The Parameterized Complexity of Abduction. Proceedings of the AAAI Conference on Artificial Intelligence, 26(1), 743-749. https://doi.org/10.1609/aaai.v26i1.8224

Issue

Vol. 26 No. 1 (2012): Twenty-Sixth AAAI Conference on Artificial Intelligence

Section

AAAI Technical Track: Knowledge Representation and Reasoning