Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Complexity classifications for propositional abduction in Post's framework
Laboratoire d'Informatique Fondamentale, Unité Mixte de Recherche, Aix-Marseille Université, France.
Laboratoire d'Informatique Fondamentale, Unité Mixte de Recherche, Aix-Marseille Université, France.
TWT GmbH, Germany.
2012 (English)In: Journal of logic and computation (Print), ISSN 0955-792X, E-ISSN 1465-363X, Vol. 22, no 5, 1145-1170 p.Article in journal (Refereed) Published
Abstract [en]

In this article, we investigate the complexity of abduction, a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining the world's behaviour, it aims at finding an explanation for some observed manifestation. In this article, we consider propositional abduction, where the knowledge base and the manifestation are represented by propositional formulæ. The problem of deciding whether there exists an explanation has been shown to be Σ2p-complete in general. We focus on formulæ in which the allowed connectives are taken from certain sets of Boolean functions. We consider different variants of the abduction problem in restricting both the manifestations and the hypotheses. For all these variants, we obtain a complexity classification for all possible sets of Boolean functions. In this way, we identify easier cases, namely NP-complete, coNP-complete and polynomial cases. Thus, we get a detailed picture of the complexity of the propositional abduction problem, hence highlighting the sources of intractability. Further, we address the problem of counting the full explanations and prove a trichotomous classification theorem.

Place, publisher, year, edition, pages
2012. Vol. 22, no 5, 1145-1170 p.
Keyword [en]
Abduction, boolean connective, computational complexity, Post's lattice, propositional logic, Boolean connectives, Knowledge base, Non-monotonic reasoning, NP Complete, Polynomial case, Knowledge based systems, Boolean functions
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:hj:diva-31620DOI: 10.1093/logcom/exr012ISI: 000309469900008Scopus ID: 2-s2.0-84866948930OAI: oai:DiVA.org:hj-31620DiVA: diva2:957134
Available from: 2016-09-01 Created: 2016-09-01 Last updated: 2016-09-01Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Schmidt, Johannes
In the same journal
Journal of logic and computation (Print)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 14 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf