Problem $P_N$ of "size" $N$: Evaluate a polynomial $a(x)=\sum_{i=0}^{N-1}a_ix^i$ of "length" $N$ (length=degree+1) at each of a set $E_N=\{a_k\}_{k=0}^{N-1}$ of $N$ distinct points $a_k \in F$ (the "evaluation points").
I am reading about this at the book "Elements of algebra and algebraic computing-J.D.Lipson".
The first algorithm that is described does N^2+O(N) multiplications, it uses Horner's rule.
After that, we have to impose some structure on the evaluation points so that we can speedup the solution. @vzn