Solving systems of polynomial inequalities in subexponential time

Let the polynomials f1,..., fk∈ ℤ[X1,..., Xn] have degrees deg (fi) < d and absolute value of any coetficient off less than or equal to 2M for all 1 ⩽ i ⩽ k. We describe an algorithm which recognises the existence of a real solution of the system of inequalities f1 ⩾ 0,..., fk ⩾ 0. In the case of a positive answer the algorithm constructs a certain finite set of solutions (which is, in fact, a representative set for the family of components of connectivity of the set of all real solutions of the system). The algorithm runs in time polynomial in M(kd) n2. The previously known upper time bound for this problem was Sh=(A1+A2log⁡Re⁡)Re⁡n.Sc1/3