Abstract of Paper |

*Subtractive Reductions and Complete Problems for Counting Complexity Classes*

by Arnaud Durand, Miki Hermann, Phokion G. Kolaitis

**Abstract:**

We introduce and investigate a new type of reductions between counting problems, which we call \emph{subtractive reductions}. We show that the main counting complexity classes \#P, \#NP, as well as all higher counting complexity classes $\#.\Pi^P_k$, $k\geq 2$, are closed under subtractive reductions. We then pursue problems that are complete for these classes via subtractive reductions. We focus on the class \#NP (which is the same as the class \#.coNP) and show that it contains natural complete problems via subtractive reductions, such as the problem of counting the minimal models of a Boolean formula in conjunctive normal form and the problem of counting the cardinality of the set of minimal solutions of a homogeneous system of linear Diophantine inequalities.