Mathematics – Algebraic Geometry
Scientific paper
2000-05-22
Mathematics
Algebraic Geometry
Complexity bounds in theorems 1, 5, and 7 corrected, along with some minor typos. Paper corresponds to three talks delivered a
Scientific paper
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, and (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 \exists\forall\exists and \exists\exists\forall\exists, 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 lectures presented at the conference corresponding to this proceedings volume. The titles of the lectures were ``Some Speed-Ups in Computational Algebraic Geometry,'' ``Diophantine Problems Nearly in the Polynomial Hierarchy,'' and ``Curves, Surfaces, and the Frontier to Undecidability.''
No associations
LandOfFree
Algebraic Geometry Over Four Rings and the Frontier to Tractability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Algebraic Geometry Over Four Rings and the Frontier to Tractability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algebraic Geometry Over Four Rings and the Frontier to Tractability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-83035