Some Speed-Ups and Speed Limits for Real Algebraic Geometry

The full text article is not available for purchase.

The publisher only permits individual articles to be downloaded by subscribers.


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 semi-algebraic 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 ℂ) only if P=NP (resp. NPBPP). The last result follows easily from an unpublished observation of S. Smale. Copyright 2000 Academic Press.

Keywords: BPP; NP; complexity; connected components; fewnomials; polylogarithmic; semi-algebraic; upper bounds

Document Type: Research Article

Affiliations: Department of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong

Publication date: September 1, 2000

Related content



Share Content

Access Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content
Cookie Policy
Cookie Policy
ingentaconnect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more