Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

On asymptotic estimates
for arithmetic cost functions


Author: Carlos Gustavo T. de A. Moreira
Journal: Proc. Amer. Math. Soc. 125 (1997), 347-353
MSC (1991): Primary 11Y16; Secondary 68Q25, 68Q15, 11B75
MathSciNet review: 1350946
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [H] 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. CMP 89:16
  • [MS] de Melo, W. and Svaiter, B.F., The cost of computing integers, Proc. Amer. Math. Soc. 124 (1996), 1377-1378. CMP 96:08
  • [SS] 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. CMP 96:10

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (1991): 11Y16, 68Q25, 68Q15, 11B75

Retrieve articles in all journals with MSC (1991): 11Y16, 68Q25, 68Q15, 11B75


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

DOI: http://dx.doi.org/10.1090/S0002-9939-97-03583-1
PII: S 0002-9939(97)03583-1
Received by editor(s): October 25, 1994
Received by editor(s) in revised form: August 15, 1995
Communicated by: Andreas R. Blass
Article copyright: © Copyright 1997 American Mathematical Society