The cost of computing integers

DOI10.1090/S0002-9939-96-03173-5zbMath0851.11054OpenAlexW1542260560MaRDI QIDQ4875601

Welington De Melo, Benar Fux Svaiter

Publication date: 24 April 1996

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0002-9939-96-03173-5

zbMATH Keywords

complexityarithmetical functionscomputing integers

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Arithmetic functions; related numbers; inversion formulas (11A25) Rate of growth of arithmetic functions (11N56)

Related Items (max. 100)

Counting arithmetic formulas ⋮ On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)? ⋮ Some integer formula encodings and related algorithms ⋮ On asymptotic estimates for arithmetic cost functions ⋮ On a generalization of addition chains: addition-multiplication chains ⋮ On solving univariate sparse polynomials in logarithmic time ⋮ Algebraic Complexity Classes

Cites Work

• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

This page was built for publication: The cost of computing integers