A comparison of Zeroes and Ones of a Boolean Polynomial
Vyalyi, M. N.
Original · EN
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.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.