On asymptotic estimates for arithmetic cost functions
HTML articles powered by AMS MathViewer
- by Carlos Gustavo T. de A. Moreira PDF
- Proc. Amer. Math. Soc. 125 (1997), 347-353 Request permission
Abstract:
Let $\tau (n)$ (the cost of $n$) be the minimum number of arithmetic operations needed to obtain $n$ starting from 1. We prove that $\tau (n)\ge \frac {\log n}{\log \log n}$ for almost all $n\in \mathbf {N}$, and, given $\varepsilon >0$, $\tau (n)\le \frac {(1+ \varepsilon )\log n}{\log \log n}$ for all $n$ sufficiently large. We prove analogous results for costs of polynomials with integer coefficients.References
- Heintz, Joos, On the Computational Complexity of Polynomials and Bilinear Mappings. A Survey, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (G. Goos and J. Hartmanis, eds.), Lecture Notes in Computer Science 356, Springer Verlag, Berlin, 1989, pp. 269–300.
- de Melo, W. and Svaiter, B.F., The cost of computing integers, Proc. Amer. Math. Soc. 124 (1996), 1377–1378.
- Shub, Michael and Smale, Steve, On the Intractability of Hilbert’s Nullstellensatz and an algebraic version of “$NP\ne P ?$”, Duke Math. J. 81 (1995), 47–54.
Additional Information
- Carlos Gustavo T. de A. Moreira
- Affiliation: Instituto de Matematica Pura e Aplicada, Estrada Dona Castorina, 110, 22460-320, Rio de Janeiro, Brasil
- Email: gugu@impa.br
- Received by editor(s): October 25, 1994
- Received by editor(s) in revised form: August 15, 1995
- Communicated by: Andreas R. Blass
- © Copyright 1997 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 125 (1997), 347-353
- MSC (1991): Primary 11Y16; Secondary 68Q25, 68Q15, 11B75
- DOI: https://doi.org/10.1090/S0002-9939-97-03583-1
- MathSciNet review: 1350946