Polynomials with Rational Coefficients Which are Hard to Compute

We present specific polynomials in 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: ∑δ = 0ᵈ e2π i/2^δ x^δ, ∑δ = 0ᵈ 22^δ x^δ. We also show that the minimum number of arithmetic operations to compute polynomials in C[x] is itself computable. Finally, we study computational complexity in finite-dimensional algebras over an algebraically closed field.