Computer Science – Computational Complexity
Scientific paper
2010-06-25
Computer Science
Computational Complexity
Scientific paper
In this paper we investigate the complexity of abduction, a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining the world's behavior it aims at finding an explanation for some observed manifestation. In this paper we consider propositional abduction, where the knowledge base and the manifestation are represented by propositional formulae. The problem of deciding whether there exists an explanation has been shown to be \SigPtwo-complete in general. We focus on formulae 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 sources of intractability. Further, we address the problem of counting the explanations and draw a complete picture for the counting complexity.
Creignou Nadia
Schmidt Johannes
Thomas Michael
No associations
LandOfFree
Complexity Classifications for Propositional Abduction in Post's Framework does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Complexity Classifications for Propositional Abduction in Post's Framework, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity Classifications for Propositional Abduction in Post's Framework will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-309690