✦ LIBER ✦
On primitive recursive algorithms and the greatest common divisor function
✍ Scribed by Yiannis N. Moschovakis
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 341 KB
- Volume
- 301
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
We establish linear lower bounds for the complexity of non-trivial, primitive recursive algorithms from piecewise linear given functions. The main corollary is that logtime algorithms for the greatest common divisor from such givens (such as Stein's) cannot be matched in e ciency by primitive recursive algorithms from the same given functions. The question is left open for the Euclidean algorithm, which assumes the remainder function.