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 (the cost of ) be the minimum number of arithmetic operations needed to obtain starting from 1. We prove that for almost all , and, given , for all sufficiently large. We prove analogous results for costs of polynomials with integer coefficients.

**[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 ``''*, Duke Math. J.**81**(1995), 47-54. CMP**96:10**

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

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