Rheinische Friedrich-Wilhelms-Universität Bonn 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

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

Powered by Zope