
Universität Bonn > Institut für Informatik > Abteilung V  
CSAPXReports 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 RSErepresentation (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 