Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 1990 Copyright 1990 University of Bonn, Department of Computer Science, 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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V