Complexity classifications for propositional abduction in Post's framework

Creignou, Nadia (author): Laboratoire d'Informatique Fondamentale, Unité Mixte de Recherche, Aix-Marseille Université, France

Schmidt, Johannes (author): Laboratoire d'Informatique Fondamentale, Unité Mixte de Recherche, Aix-Marseille Université, France

(creator_code:org_t)

2011-07-07
2012
English.
In: Journal of logic and computation (Print). - : Oxford University Press (OUP). - 0955-792X .- 1465-363X. ; 22:5, s. 1145-1170

Related links:: http://arxiv.org/pdf...; show more...; https://urn.kb.se/re...; https://doi.org/10.1...; show less...

Abstract Subject headings

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.

By the author/editor: Creignou, Nadia; Schmidt, Johanne ...; Thomas, Michael

About the subject

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.