ON THE CELL PROBE COMPLEXITY OF POLYNOMIAL EVALUATION

We consider the cell probe complexity of the polynomial evaluation pro blem with preprocessing of coefficients, for polynomials of degree at most n over a finite field K. We show that the trivial cell probe algo rithm for the problem is optimal if K is sufficiently large compared t o n. As an application, we give a new proof of the fact that P not equ al incr-TIME (o(log n/log log n)).