We exhibit a new method for showing lower bounds for the time complexity of polynomial evaluation procedures. Time, denoted
by
L, is measured in terms of nonscalar arithmetic operations. The time complexity function considered in this paper is
L
2. In contrast with known methods for proving lower complexity bounds, our method is purely combinatorial and does not require
powerful tools from algebraic or diophantine geometry.
By means of our method we are able to verify the computational hardness of new natural families of univariate polynomials
for which this was impossible up to now. By computational hardness we mean that the complexity function L
2 grows linearly in the degree of the polynomials of the family we are considering.
Our method can also be applied to classical questions of transcendence proofs in number theory and geometry. A list of (old
and new) formal power series is given whose transcendency can be shown easily by our method.
Work partially supported by Spanish DGCYT grant PB 96-0671-C02-02.