Complexity of Propositional Abduction for Restricted Sets of Boolean Functions

Details Complexity of Propositional Abduction for Restricted Sets of Boolean Functions Complexity of Propositional Abduction for Restricted Sets of Boolean Functions

2009-12-16

arxiv.org/abs/0912.3134v4

Computer Science

Computational Complexity

Proceedings version, the journal version is available at http://arxiv.org/abs/1006.4923

Scientific paper

Abduction is a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining how the world behaves it aims at finding an explanation for some observed manifestation. In this paper we focus on 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 SigmaP2-complete in general. We consider variants obtained by restricting the allowed connectives in the formulae to certain sets of Boolean functions. We give a complete classification of the complexity for all considerable sets of Boolean functions. In this way, we identify easier cases, namely NP-complete and polynomial cases; and we highlight sources of intractability. Further, we address the problem of counting the explanations and draw a complete picture for the counting complexity.

Affiliated with

Also associated with

No associations

Rating

Complexity of Propositional Abduction for Restricted Sets of Boolean Functions 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 of Propositional Abduction for Restricted Sets of Boolean Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Propositional Abduction for Restricted Sets of Boolean Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-48987