Complexity of some arithmetic problems for binary polynomials |
| |
Authors: | Eric Allender Anna Bernasconi Carsten Damm Joachim von zur Gathen Michael Saks Igor Shparlinski |
| |
Affiliation: | (1) Department of Computer Science, Rutgers University, Piscataway, NJ 08854-8019, USA;(2) Dipartimento di Informatica, Università di Pisa, 56127 Pisa, Italy;(3) Institut für Numerische und Angewandte Mathematik, Universität Göttingen, 37083 Göttingen, Germany;(4) Fakultät für Elektrotechnik, Informatik und Mathematik, Universität Paderborn, 33095 Paderborn, Germany;(5) Mathematics Department, Rutgers University, Piscataway, NJ 08854-8019, USA;(6) Department of Computing, Macquarie University, NSW, 2109, Australia |
| |
Abstract: | We study various combinatorial complexity measures of
Boolean functions related to some natural arithmetic problems about
binary polynomials, that is, polynomials over
.
In particular, we consider
the Boolean function deciding whether a given polynomial over
is squarefree. We obtain an exponential lower bound on the size of a
decision tree for this function, and derive an asymptotic formula, having
a linear main term, for its average sensitivity. This allows us to estimate
other complexity characteristics such as the formula size, the average decision
tree depth and the degrees of exact and approximative polynomial
representations of this function. Finally, using a different method, we
show that testing squarefreeness and irreducibility of polynomials over
cannot be done in
for any odd prime p. Similar results are
obtained for deciding coprimality of two polynomials over
as well. |
| |
Keywords: | ((no )) |
本文献已被 SpringerLink 等数据库收录! |
|