The Computational Complexity of (XOR, AND)-Counting Problems

TitleThe Computational Complexity of (XOR, AND)-Counting Problems
Publication TypeTechnical Report
Year of Publication1990
AuthorsEhrenfeucht, A., & Karpinski M.
Other Numbers597

We characterize the computational complexity of counting the exact number of satisfying assignments of (XOR, AND)-formulas in their RSE-representation (i.e., equivalently, polynomials in GF[2] [x subscript 1, ..., x subscript n]. This problem refrained for some time efforts to find a polynomial time solution and 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 [Karpinski, Luby 89] the counting problem for arbitrary multivariate polynomials over GF[2] has been proved to have randomized polynomial time approximation algorithms.

Bibliographic Notes

ICSI Technical Report TR-90-033

Abbreviated Authors

A. Ehrenfeucht and M. Karpinski

ICSI Publication Type

Technical Report