Some speed-ups and speed limits for real algebraic geometry (Q1594829)

The main result of the paper (theorem 1.1) is an upper bound for the number of connected components of a semialgebraic set \(S\) defined by a system of polynomial equations and (strict) inequalities. The bound is linear in the normalized volume of a suitable polytope associated to the exponents of the monomials occurring in the equations defining \(S\) and single exponential in the number of inequalities taking part in the definition of \(S\). Moreover the bound contains an exponential extra factor of \(2^n\). In terms of the number of monomials occurring in the equations defining \(S\) this bound is single exponential, but independent of the degree of the equations (theorem 3.5). Another result of the paper is an algorithm for the approximation of all real roots of a \(k\)-sparse univariate standard or exponential polynomial of degree \(d\) in a given interval. The execution time of this algorithm is linear in \(k\log d\) (theorem 1.3). Finally the author enumerates a series of algorithmic problems of geometric nature whose solution in polynomial time would imply \(P=\text{NP}\).