Publication Details
Title: The Computational Complexity of (XOR, AND)-Counting Problems
Author: A. Ehrenfeucht and M. Karpinski
Group: ICSI Technical Reports
Date: July 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-033.pdf
Overview:
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 Information:
ICSI Technical Report TR-90-033
Bibliographic Reference:
A. Ehrenfeucht and M. Karpinski. The Computational Complexity of (XOR, AND)-Counting Problems. ICSI Technical Report TR-90-033, July 1990
Author: A. Ehrenfeucht and M. Karpinski
Group: ICSI Technical Reports
Date: July 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-033.pdf
Overview:
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 Information:
ICSI Technical Report TR-90-033
Bibliographic Reference:
A. Ehrenfeucht and M. Karpinski. The Computational Complexity of (XOR, AND)-Counting Problems. ICSI Technical Report TR-90-033, July 1990