×

Solving systems of polynomial inequalities in subexponential time. (English) Zbl 0662.12001

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)}}\).
Reviewer: J.Liang

MSC:

12-04 Software, source code, etc. for problems pertaining to field theory
68Q25 Analysis of algorithms and problem complexity
12D15 Fields related with sums of squares (formally real fields, Pythagorean fields, etc.)
14Pxx Real algebraic and real-analytic geometry
11R09 Polynomials (irreducibility, etc.)
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chistov, A. L.; Grigor’ev, D. Yu, Polynomial-time factoring of multivariable polynomials over a global field, (Preprint LOMI E-5-82, Leningrad (1982)) · Zbl 0509.68029
[2] Chistov, A. L.; Grigor’ev, D. Yu., Subexponential-time solving systems of algebraic equations. I, (Preprint LOMI E-9-83, Leningrad (1983)) · Zbl 0596.12021
[3] Chistov, A. L.; Grigor’ev, D. Yu., Subexponential-time solvhlg systems of algebraic equations. II, (Preprint LOMI E-10-83, Leningrad (1983)) · Zbl 0596.12021
[4] Chistov, A. L., Polynomial-time factoring of polynomials and finding compounds of a variety within subexponential time, (Notes of Sci. Seminars of Leningrad Department of Math. Steklov Inst., 137 (1984)), 124-188, (in Russian, English transl, to appear in J. Soviet Math.) · Zbl 0561.12010
[5] Chistov, A. L.; Grigor’ev, D. Yu., Complexity of quantifier elimination in the theory of algebraically closed fields, Springer Lec. Notes Comp. Sci, 176, 17-31 (1984) · Zbl 0562.03015
[6] Collins, G. E., Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Springer Lec. Notes Comp. Sci., 33, 134-183 (1975) · Zbl 0318.02051
[7] Grigor’ev, D. Yu., Factoring multivariable polynomials over a finite field and solving systems of algebraic equations, Notes of Sci. Seminars of Leningrad Department of Math. Steklov Inst., 137, 20-79 (1984), (in Russian, English transl, to appear in J. Soviet Math.) · Zbl 0561.12011
[8] Grigor’ev, D. Yu., Computational complexity in polynomial algebra, (Proc. Intern. Congress of Mathematicians, Berkeley (1987)) · Zbl 0667.68054
[9] Heindel, L. E., Integer arithmetic algorithms for polynomial real zero determination, J. Assoc. Comp. Mach, 18, 4, 533-548 (1971) · Zbl 0226.65039
[10] Heintz, J., Definability and fast quantifier elimination in algebraically closed field, Theor. Comp. Sci, 24, 239-278 (1983) · Zbl 0546.03017
[11] Khachian, L. G., A polynomial algorithm in linear programming, Soviet Math. Doklady, 20, 1, 191-194 (1979) · Zbl 0409.90079
[12] Lang, S., Algebra (1965), Addison-Wesley: Addison-Wesley New York · Zbl 0193.34701
[13] Lenstra, A. R., Factoring multivariable polynomials over algebraic number fields, Springer Lec. Notes Comp. Sci, 176, 389-396 (1984) · Zbl 0568.12001
[14] Milnor, J., On the Betti numbers of real varieties, Proc. Amer. Math. Soc, 15, 2, 275-280 (1964) · Zbl 0123.38302
[15] Milnor, J., Topology from the Differentiable Viewpoint (1965), University Press of Virginia · Zbl 0136.20402
[16] Mignotte, M., An inequality about factors of polynomials, Math. Comput, 28, 128, 1153-1157 (1974) · Zbl 0299.12101
[17] Shafarevieh, I. R., Basic Algebraic Geometry (1974), Springer-Verlag: Springer-Verlag Berlin · Zbl 0284.14001
[18] Tarski, A., A Decision Method for Elementary Algebra and Geometry (1951), University of California Press · Zbl 0044.25102
[19] Thorpe, J. A., Elementary Topics in Differential Geometry (1979), Springer-Verlag: Springer-Verlag Berlin · Zbl 0404.53001
[20] Vorobjov, N. N., Bounds of real roots of a system of algebraic equations, (Notes of Sci. Seminars of Leningrad Department of Math. Steklov Inst., 137 (1984)), 7-19, (in Russian, English transl, to appear in J. Soviet Math.) · Zbl 0546.65027
[21] Vorobjov, N. N.; Grigor’ev, D. Yu., Finding real solutions of systems of algebraic inequalities within the subexponential time, Soviet Math. Dokl., 32, 1, 316-320 (1985) · Zbl 0607.65027
[22] Wüthrich, H. R., Ein Entscheidungsverfahren ffir die Theorie der reell-abgeschlassenen Kbrper, In: Komplexitt von Entschiedungs Problemen, (Specker, E, Strassen, V., Eds). Springer Lec. Notes Comp. Sci, 43, 138-162 (1976) · Zbl 0363.02052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.