×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chistov, A.L.; Grigor’ev, D.Yu, Polynomial-time factoring of multivariable polynomials over a global field, () · Zbl 0509.68029
[2] Chistov, A.L.; Grigor’ev, D.Yu., Subexponential-time solving systems of algebraic equations. I, () · Zbl 0596.12021
[3] Chistov, A.L.; Grigor’ev, D.Yu., Subexponential-time solvhlg systems of algebraic equations. II, () · Zbl 0596.12021
[4] Chistov, A.L., Polynomial-time factoring of polynomials and finding compounds of a variety within subexponential time, (), 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)
[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, () · 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 New York
[13] Lenstra, A.R., Factoring multivariable polynomials over algebraic number fields, Springer lec. notes comp. sci, 176, 389-396, (1984)
[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 Berlin
[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 Berlin · Zbl 0404.53001
[20] Vorobjov, N.N., Bounds of real roots of a system of algebraic equations, (), 7-19, (in Russian, English transl, to appear in J. Soviet Math.)
[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: komplexit t von entschiedungs problemen, (Specker, E, Strassen, V., eds). Springer lec. notes comp. sci, 43, 138-162, (1976)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.