ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Theorem 3.28. [4] <s> Once we have developed an algorithm (q.v.) for solving a computational problem and analyzed its worst-case time requirements as a function of the size of its input (most usefully, in terms of the O-notation; see ALGORITHMS, ANALYSIS OF), it is inevitable to ask the question: "Can we do better?" In a typical problem, we may be able to devise new algorithms for the problem that are more and more efficient. But eventually, this line of research often seems to hit an invisible barrier, a level beyond whch improvements are very difficult, seemingly impossible, to come by. After many unsuccessful attempts, algorithm designers inevitably start to wonder if there is something inherent in the problem that makes it impossible to devise algorithms that are faster than the current one. They may try to develop mathematical techniques for proving formally that there can be no algorithm for the given problem which runs faster than the current one. Such a proof would be valuable, as it would suggest that it is futile to keep working on improved algorithms for this problem, that further improvements are certainly impossible. The realm of mathematical models and techniques for establishing such impossibility proofs is called computational complexity. <s> BIB001 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Theorem 3.28. [4] <s> 1 Introduction.- 2 Definitions and First Properties of Computation.- 3 Computation over a Ring.- 4 Decision Problems and Complexity over a Ring.- 5 The Class NP and NP-Complete Problems.- 6 Integer Machines.- 7 Algebraic Settings for the Problem "P ? NP?".- 8 Newton's Method.- 9 Fundamental Theorem of Algebra: Complexity Aspects.- 10 Bezout's Theorem.- 11 Condition Numbers and the Loss of Precision of Linear Equations.- 12 The Condition Number for Nonlinear Problems.- 13 The Condition Number in ?(H(d).- 14 Complexity and the Condition Number.- 15 Linear Programming.- 16 Deterministic Lower Bounds.- 17 Probabilistic Machines.- 18 Parallel Computations.- 19 Some Separations of Complexity Classes.- 20 Weak Machines.- 21 Additive Machines.- 22 Nonuniform Complexity Classes.- 23 Descriptive Complexity.- References. <s> BIB002 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Theorem 3.28. [4] <s> Given a quadratic map $$Q:\mathbb{K}^n \to \mathbb{K}^k $$ defined over a computable subring D of a real closed field $$\mathbb{K},$$ and p ?D[Y1,...,Yk] of degree d, we consider the zero set $$Z = Z(p(Q(X)), \mathbb{K}^n) \subseteq \mathbb{K}^n$$ of p(Q(X1,...,Xn)) ?D[X1,...,Xn]. We present a procedure that computes, in (dn)O(k) arithmetic operations in D, a set $$\mathcal{S}$$ of (real univariate representations of) sampling points in $$\mathbb{K}^n$$ that intersects nontrivially each connected component of Z. As soon as k=o(n), this is faster than the known methods that all have exponential dependence on n in the complexity. In particular, our procedure is polynomial-time for constant k. In contrast, the best previously known procedure is only capable of deciding in $$n^{O(k^2 )} $$ operations the nonemptiness (rather than constructing sampling points) of the set Z in the case of p(Y)=?iYi2 and homogeneous Q. ::: ::: A by-product of our procedure is a bound (dn)O(k) on the number of connected components of Z. ::: ::: The procedure consists of exact symbolic computations in D and outputs vectors of algebraic numbers. It involves extending $$\mathbb{K}$$ by infinitesimals and subsequent limit computation by a novel procedure that utilizes knowledge of an explicit isomorphism between real algebraic sets. <s> BIB003
There exists an algorithm which decides if a given system of inequalities Barvinok's algorithm did not produce explicit sample points meeting every semialgebraically connected component of the set of solutions (in the style of Theorem 2.15 in the general case). This was done by Grigoriev and Pasechnik BIB003 . In fact, they consider the following more general situation. Let S ⊂ R k be the pull-back of a P-semi-algebraic subset T ⊂ R via a qua- In BIB003 , Grigoriev and Pasechnik give an algorithm that computes a set of sample points guaranteed to meet every semi-algebraically connected component of S whose complexity is bounded by (ksd) O( ) where s = card P, and d is a bound on the degrees of the polynomials in P. Remark 3.29. Note that the problem of deciding the feasibility of even one quartic real polynomial equation is an NP-hard problem, and the same is true for systems of quadratic equations. Thus, there is little hope for obtaining a polynomial-time algorithm for either of these problems. The above results are somewhat surprising in that they imply in the quadratic case one obtains polynomial time algorithms for testing feasibility, provided the number of polynomials is kept fixed (see also Section 3.6.3 below). We refer the reader to BIB001 and BIB002 for precise definitions of the computational complexity classes that we refer to here and elsewhere in this survey.