摘要：Given a polynomial $f$ with coefficients from a field $\field$,is it easier to compute $f$ over an extension ring $R$ than over $\field$?We address this question, and show the following.For every polynomial $f$, there is a noncommutative extension ring $R$of the field $\field$ such that $\field$ is in the center of $R$and $f$ has a polynomial-size formula over $R$. On the other hand, if $\field$ is algebraically closed,no commutative extension ring $R$ can reduce formula or circuit complexity of $f$.To complete the picture, we prove that over any field,there exist hard polynomials with zero-one coefficients. (This is a basic theorem, but we could not find it written explicitly.)Finally, we show that low-dimensional extensions are not very helpful in computing polynomials.As a corollary, we obtain that the elementary symmetric polynomials have formulas of size $n^{O(\log \log n)}$ over any field, and that division gates can be efficiently eliminated from circuits, over any field.
