Mathematics – Algebraic Geometry
Scientific paper
1999-05-02
Mathematics
Algebraic Geometry
This is the final journal version which will appear in Journal of Complexity. More typos are corrected, and a new section is a
Scientific paper
We give new positive and negative results (some conditional) on speeding up computational algebraic geometry over the reals: (1) A new and sharper upper bound on the number of connected components of a semialgebraic set. Our bound is novel in that it is stated in terms of the volumes of certain polytopes and, for a large class of inputs, beats the best previous bounds by a factor exponential in the number of variables. (2) A new algorithm for approximating the real roots of certain sparse polynomial systems. Two features of our algorithm are (a) arithmetic complexity polylogarithmic in the degree of the underlying complex variety (as opposed to the super-linear dependence in earlier algorithms) and (b) a simple and efficient generalization to certain univariate exponential sums. (3) Detecting whether a real algebraic surface (given as the common zero set of some input straight-line programs) is not smooth can be done in polynomial time within the classical Turing model (resp. BSS model over C) only if P=NP (resp. NP<=BPP). The last result follows easily from an unpublished result of Steve Smale.
No associations
LandOfFree
Some Speed-Ups and Speed Limits for Real Algebraic Geometry 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 Some Speed-Ups and Speed Limits for Real Algebraic Geometry, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some Speed-Ups and Speed Limits for Real Algebraic Geometry will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-295718