Complexity of Propositional Abduction for Restricted Sets of Boolean Functions.
Nadia CreignouJohannes SchmidtMichael ThomasPublished in: KR (2010)
Keyphrases
- boolean functions
- prime implicants
- polynomial size
- multi valued
- uniform distribution
- propositional knowledge base
- conjunctive normal form
- propositional formulas
- threshold functions
- abductive reasoning
- dnf formulae
- relevant variables
- functional properties
- bounded treewidth
- membership queries
- boolean formula
- prime implicates
- computational complexity
- propositional logic
- background knowledge
- worst case
- first order logic
- np complete
- logic programming
- lower bound