@article{doi:10.1137/0203010,
    Abstract = {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.},
    Author = {Strassen, Volker},
    EPrint = {https://doi.org/10.1137/0203010},
    File = {Polynomials with Rational Coefficients Which are Hard to Compute - strassen1974.pdf},
    Journal = {SIAM Journal on Computing},
    Number = {2},
    Pages = {128-149},
    Title = {Polynomials with Rational Coefficients Which are Hard to Compute},
    URL = {https://doi.org/10.1137/0203010},
    Volume = {3},
    Year = {1974},
    bdsk-url-1 = {https://doi.org/10.1137/0203010},
    date-added = {2023-09-15 16:53:00 +0200},
    date-modified = {2023-09-15 16:53:00 +0200},
    doi = {10.1137/0203010}
}

@article{doi:10.1137/0203010, Abstract = {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\, Author = {Strassen, Volker}, EPrint = {https://doi.org/10.1137/0203010}, File = {Polynomials with Rational Coefficients Which are Hard to Compute - strassen1974.pdf}, Journal = {SIAM Journal on Computing}, Number = {2}, Pages = {128-149}, Title = {Polynomials with Rational Coefficients Which are Hard to Compute}, URL = {https://doi.org/10.1137/0203010}, Volume = {3}, Year = {1974}, bdsk-url-1 = {https://doi.org/10.1137/0203010}, date-added = {2023-09-15 16:53:00 +0200}, date-modified = {2023-09-15 16:53:00 +0200}, doi = {10.1137/0203010} }}^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.