Algebraic geometry over four rings and the frontier to tractability
J. Maurice Rojas · Contemporary mathematics - American Mathematical Society · 2000
We present some new and recent algorithmic results concerning polynomial system solving over various rings. In particular, we present some of the best recent bounds on: (a) the complexity of calculating the complex dimension of an algebraic set (b) the height of the zero-dimensional part of an algebraic set over C (c) the number of connected components of a semi-algebraic set We also present some results which significantly lower the complexity of deciding the emptiness of hypersurface intersections over C and Q, given the truth of the Generalized Riemann Hypothesis. Furthermore, we state some recent progress on the decidability of the prefixes 989 and 9989, quantified over the positive integers. As an application, we conclude with a result connecting Hilbert's Tenth Problem in three variables and height bounds for integral points on algebraic curves. This paper is based on three invited lectures presented at the conference corresponding to this proceedings volume. The tit...