Solving systems of polynomial inequalities in subexponential time (Q1113939)

The authors developed a subexponential time algorithm to find real solutions of systems of polynomial inequalities. A method of finding real roots of a polynomial was introduced as a starting point of the algorithm and the general case was reduced to this case. Theoretical background of the algorithm was given in details in the paper while a general outline of the algorithm was provided. The algorithm has a running time bounded by \(M(kd)^{n^ 2}\), where k is the number of polynomials with degrees less than d and coefficients not exceeding \(2^ M\), n is the number of the variables. The previously known upper bound for this problem was \((Mkd)^{2^{O(n)}}\).