On the counting complexity of propositional circumscription
Propositional circumscription, asking for the minimal models of a Boolean formula, is an important problem in artificial intelligence, in data mining, in coding theory, and in the model checking based procedures in automated reasoning. We consider the counting problems of propositional circumscription for several subclasses with respect to the structure of the formula. We prove that the counting problem of propositional circumscription for dual Horn, bijunctive, and affine formulas is #P-complete for a particular case of Turing reduction, whereas for Horn and 2affine formulas it is in FP. As a corollary, we obtain also the #P-completeness result for the counting problem of hypergraph transversal. (c) 2007 Elsevier B.V. All rights reserved.
counting complexity propositional circumscription dual horn horn bijunctive and affine formulas hypergraph transversal computational complexity