The Computational Complexity of ({\it XOR, AND/})-Counting Problems
Andrzej Ehrenfeucht, Marek Karpiński · 1990
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.