Solving systems of polynomial inequalities in subexponential time.

*(English)*Zbl 0662.12001The 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 |

##### Keywords:

algebraic complexity; subexponential time algorithm; real solutions of systems of polynomial inequalities
PDF
BibTeX
XML
Cite

\textit{D. Yu. Grigor'ev} and \textit{N. N. Vorobjov jun.}, J. Symb. Comput. 5, No. 1--2, 37--64 (1988; Zbl 0662.12001)

Full Text:
DOI

**OpenURL**

##### 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.