Polynomials with Rational Coefficients Which are Hard to Compute
Volker Strassen · SIAM Journal on Computing · 1974
We present specific polynomials in $\mathbb{C}[x]$ with algebraic or rational coefficients which are hard to compute (even though arbitrary complex numbers are allowed as inputs for the computation). Examples are: $\sum_{\delta = 0}^d e^{2\pi i/2^\delta } x^\delta $, $\sum_{\delta = 0}^d 2^{2^\delta } x^\delta $. We also show that the minimum number of arithmetic operations to compute polynomials in $\mathbb{C}[x]$ is itself computable. Finally, we study computational complexity in finite-dimensional algebras over an algebraically closed field.