×

Finding connected components of a semialgebraic set in subexponential time. (English) Zbl 0783.14036

Let a semialgebraic set be given by a quantifier free formula of the first order theory of real closed fields with \(k\) atomic subformulas of type \(f \geq 0\), where the polynomials \(f\) have \(n\) variables, are of degree less than \(d\), with (integer) coefficients whose bit length is bounded by \(M\). The size of the semialgebraic set is then estimated by the bound \(L=Mkd^ n\). The main result in the paper is an algorithm that finds the connected components of the given semialgebraic set in time \(M^{0(1)}(kd)^{n^{0(1)}}\) (therefore it runs in subexponential time in terms of the size \(L)\). The number of components is less than \((kd)^{0(n)}\), and the output will be a certain quantifier free formula with less than \((kd)^{n^{0(1)}}\) atomic subformula of the type \(g \geq 0\) for each connected component, where \(g\) is a polynomial in \(n\) variables, of degree less than \((kd)^{n^{0(1)}}\) and coefficient bit lengths less than \(M(kd)^{n^{0(1)}}\).
Actually, the results in the paper are formulated in a more general setting, namely allowing more general coefficients for the defining polynomials describing the semialgebraic set. The presented algorithms rely on much previous work, in particular requiring fast (subexponential- time) quantifier elimination and decidability algorithms of the theory of real closed fields, and algorithms for finding irreducible components of algebraic varieties over algebraically closed fields.

MSC:

14P10 Semialgebraic sets and related spaces
68Q25 Analysis of algorithms and problem complexity
12D15 Fields related with sums of squares (formally real fields, Pythagorean fields, etc.)
68W30 Symbolic computation and algebraic computation
03C10 Quantifier elimination, model completeness, and related topics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Grigor’ev, D.Yu., Vorobjov, N.N., jr.: Solving systems of polynomial inequalities in subexponential time. J. Symb. Comput.5, 37–64 (1988) · Zbl 0662.12001 · doi:10.1016/S0747-7171(88)80005-1
[2] Grigor’ev, D.Yu.: Complexity of deciding Tarski algebra. J. Symb. Comput.5, 65–108 (1988) · Zbl 0689.03021 · doi:10.1016/S0747-7171(88)80006-3
[3] Tarski, A.: A desision method for elementary algebra and geometry. University of California Press 1951 · Zbl 0044.25102
[4] Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Lecture Notes Comp. Sci. Vol. 33, pp. 134–183. Berlin, Heidelberg, New York: Springer 1975 · Zbl 0318.02051
[5] Wüthrich, H.R.: Ein Entscheidungsverfahren für die Theorie der reell-abgeschlossenen Körper. Lecture Notes Comp. Sci. Vol. 43, pp. 138–162. Berlin, Heidelberg, New York: Springer 1976 · Zbl 0363.02052
[6] Chistov, A.L., Grigor’ev, D.Yu.: Subexponential-time solving systems of algebraic equations. I. II. Preprints LOMI E-9-83 and E-10-83, Leningrad 1983
[7] Grigor’ev, D.Yu.: Computational complexity in polynomial algebra. Proceedings of the 29th Int. Congress of Mathematicians. Berkeley, pp. 1452–1460 (1986)
[8] Lang, S.: Algebra. New York: Addison-Wesley 1965 · Zbl 0193.34701
[9] Fitchos, N., Galligo, A., Morgenstern, J.: Algorithmes rapides en séquential et en parallele pour l’élimination de quantificateurs en géométrie élémentaire. VER de Mathématiques Université de Paris VII (1988)
[10] Vorobjov, N.N., jr.: Deciding consistency of systems of polynomial in exponent inequalities in subexponejitial time. Notes of Sci. Seminars of Leningrad Department of Math. Steklov Inst.176, 3–52 (in Russian) (1989)
[11] Shafarevich, I.R.: Basic algebraic geometry. Berlin, Heidelberg, New York: Springer 1974 · Zbl 0284.14001
[12] Heintz, J.: Definability and fast quantifier elimination in algebraically closed field. Theor. Comp. Sci.24, 239–278 (1983) · Zbl 0546.03017 · doi:10.1016/0304-3975(83)90002-6
[13] Vorobjov, N.N., jr., Grigor’ev, D.Yu.: Counting connected components of a semialgebraic set in subexponential time. Sov. Math. Dokl.42(2), 563–566 (1991)
[14] Dold, A.: Lectures on algebraic topology. Berlin, Heidelberg, New York: Springer 1972 · Zbl 0234.55001
[15] Grigor’ev, D.Yu., Vorobjov, N.N., jr.: Counting connected components of a semialgebraic set in subexponential time. Submitted to Computational Complexity 1989
[16] Heintz, J., Roy, M.-F., Solerno, P.: Sur la complexité du principe de Tarski-Seidenberg. Bull. Soc. Math. France.118, 101–126 (1990)
[17] Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals. Parts I-II. Technical report, Cornell University 1989 · Zbl 0676.65045
[18] Canny, J.F.: The complexity of robot motion planning. Cambridge: MIT Press 1988 · Zbl 0668.14016
[19] Grigor’ev, D.Yu., Heintz, J., Roy, M.-F., Solerno, P., Vorobjov, N.N., jr.: Comptage des composantes connexes d’un ensemble semi-algebrique en temps simplement exponential. CompteRendus Acad. Sci. Paris311, Serié I, 879–822 (1990)
[20] Heintz, J., Roy, M.-F., Solerno, P.: Construction de chamins dans un ensemble semi-algebrique. Preprint Univ. Buenos Aires, Argentina 1990
[21] Heintz, J., Roy, M.-F., Solerno, P.: Single exponential path finding in semialgebraic sets. Proc. AAECC Conf. Tokyo 1990 · Zbl 0921.14039
[22] Heintz, J., Roy, M.-F., Solerno, P.: Description des composantes connexes d’un ensemble semi-algebrique en temps simplement exponentiel. Compte-Rendus Acad. Sci. Paris313, Serié I, 167–170 (1991)
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.