A comparison of Zeroes and Ones of a Boolean Polynomial

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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

Keywords

Computational Complexity, F.1.3

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/30929

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0111052
 http://arxiv.org/abs/cs/0111052

Collections

arXiv