Finding connected components of a semialgebraic set in subexponential time

Let a semialgebraic set be defined by a quantifier-free formula with atomic subformulas of the form f_i>0, 0,1 i where the polynomials f_iX₁,..., X_n] of degree deg (f_i)<d have absolute value of the coefficients at most 2^M. An algorithm is constructed which finds the connected components of the semialgebraic set (i.e., giving formulas for them) in a time that is polynomial inM (kd) ^ro(1). Collins' previously known method has a bound which is polynomial inM (kd) ^ro(1).Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 192, pp. 3–46, 1991.