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.