A comparison of Zeroes and Ones of a Boolean Polynomial

Abstract

In this paper we consider the computational complexity of the following problem. Let $f$ be a Boolean polynomial. What value of $f$, 0 or 1, is taken more frequently? The problem is solved in polynomial time for polynomials of degrees 1,2. The next case of degree 3 appears to be PP-complete under polynomial reductions in the class of promise problems. The proof is based on techniques of quantum computation.

LaTeX2e, 6 pages