The cost of computing integers

DOI10.1090/S0002-9939-96-03173-5MaRDI QIDQ4875601zbMATH OpenOpenAlexFDO

Authors Welington de Melo, B. F. 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

arithmetical functionscomplexitycomputing integers

Mathematics Subject Classification ID

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

Recommendations

• On asymptotic estimates for arithmetic cost functions
• scientific article; zbMATH DE number 4035133
• Valiant's model and the cost of computing integers
• scientific article; zbMATH DE number 7663176

Cites work

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

Cited in

(13)

• Counting arithmetic formulas
• On solving univariate sparse polynomials in logarithmic time
• Valiant's model and the cost of computing integers
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• On a generalization of addition chains: addition-multiplication chains
• Algebraic complexity classes
• scientific article; zbMATH DE number 4035133 (Why is no real title available?)
• Some integer formula encodings and related algorithms
• On asymptotic estimates for arithmetic cost functions
• scientific article; zbMATH DE number 1929948 (Why is no real title available?)
• On the number of arithmetic formulas
• scientific article; zbMATH DE number 7663176 (Why is no real title available?)
• Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4875601)