Institut für Informatik   Abteilung V

 Universität Bonn -> Institut für Informatik -> Abteilung V CS-APX-Reports 1990 Copyright 1990 Universität Bonn, Institut für Informatik, Abt. V 894 The Computational Complexity of ({\it XOR, AND\, })-Counting Problems Andrzej Ehrenfeucht, Marek Karpinski [Download PostScript] [Download PDF] We characterize the computational complexity of counting the exact number of satisfying assignments in ($\XOR, \AND$)-formulas in their RSE-representation (i.e., equivalently, polynomials in $GF[2][x_1,\ldots,x_n]$). This problem refrained for some time effords to find a polynomial time solution and the efforts to prove the problem to be $\#P$-complete. Both main results can be generalized to the arbitrary finite fields GF[$q$]. Because counting the number of solutions of polynomials over finite fields is generic for many other algebraic counting problems, the results of this paper settle a border line for the algebraic problems with a polynomial time counting algorithms and for problems which are $\#P$-complete. In \cite{KL89} the couting problem for arbitrary multivariate polynomials over GF[2] has been proved to have randomized polynomial time approximation algorithms. Last Change: 11/05/14 at 09:13:15  English Universität Bonn -> Institut für Informatik -> Abteilung V