Arithmetic complexity
Published in ACM Transactions on Computational Logic • Jan 1, 2009
Authors:,
Lou van den Dries
Yiannis N. Moschovakis
Abstract
We obtain lower bounds on the cost of computing various arithmetic functions and deciding various arithmetic relations from specified primitives. This includes lower bounds for computing the greatest common divisor and deciding coprimeness of two integers, from primitives like addition, subtraction,...
Finding related papers...
Discussions
(0)No comments yet
Be the first to share your thoughts!