Syllabus for L. van den Dries's lectures at the
Fall school(Sept.'02)

Model theory and algorithms

---

Part 1. Elementary model theory and complexity in arithmetic.

Using basic model theory one can easily show that the greatest common divisor of two integers cannot be obtained in a uniformly bounded number of steps from those integers using arithmetic operations. This result can be used to answer a question of Moschovakis: no primitive recursive algorithm for computing the greatest common divisor and using the arithmetic operations as givens can match in efficiency the Euclidean algorithm. The unboundedness can be improved using a result from transcendental number theory, and yields in certain models of computation a triple logarithmic lower bound for the complexity of any algorithm that computes the greatest common divisor.

Part 2. Solving linear equations for polynomials with integer coefficients.

This concerns the PhD thesis of Matthias Aschenbrenner, for which he was awarded the Sacks prize. Until his work the algorithms that solved linear equations in polynomial rings over the ring of integers produced Ackermann type bounds. There had even been speculation that such non-primitive recursive bounds were unavoidable. A completely new approach by Aschenbrenner led to double exponential bounds, and these cannot be drastically improved. Note that ideal membership in polynomial rings over the ring of integers (equivalently, the word problem for commutative rings) is a family of linear equations of the kind considered, and in this form the problem originates with Kronecker.