A comparison of Zeroes and Ones of a Boolean Polynomial
| dc.creator | Vyalyi, M. N. | |
| dc.date | 2001-11-20 | |
| dc.date.accessioned | 2026-07-07T03:17:58Z | |
| dc.date.available | 2026-07-07T03:17:58Z | |
| dc.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. | |
| dc.description | LaTeX2e, 6 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0111052 | |
| dc.identifier | http://arxiv.org/abs/cs/0111052 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30929 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | A comparison of Zeroes and Ones of a Boolean Polynomial | |
| dc.type | text |