Abstract: | Let m= (1,..., m) denote an ordered field, where i+1>0 is infinitesimal relative to the elements of i, 0 < –i < m (by definition, 0= ). Given a system of inequalities f1 > 0, ..., fs > 0, fs+1 0, ..., fk 0, where fj m [X1,..., Xn] are polynomials such that, and the absolute value of any integer occurring in the coefficients of the fjs is at most 2M. An algorithm is constructed which tests the above system of inequalities for solvability over the real closure of m in polynomial time with respect to M, ((d)nd0)n+m. In the case m=, the algorithm explicitly constructs a family of real solutions of the system (provided the latter is consistent). Previously known algorithms for this problem had complexity of the order ofM(d d0m2U(n).Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Maternaticheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 174, pp. 3–36, 1988. |