Sur la complexité du principe de Tarski-Seidenberg

Heintz, Joos; Roy, Marie-Françoise; Solernó, Pablo

Bulletin de la Société Mathématique de France, Tome 118 (1990) no. 1, pp. 101-126.

[1] Ben-Or (M.), Kozen (D.), Reif (J.). - The complexity of elementary algebra and geometry, J. of Computation and Systems Sciences, t. 32, 1986, p. 251-264. | MR | Zbl

[2] Berkowitz (S.J.). - On computing the determinant in small parallel time using a small number of processors, Information Processing Letter, t. 18, 1984, p. 147-150. | MR | Zbl

[3] Bochnak (J.), Coste (M.), Roy (M.-F.). - Géométrie algébrique réelle. - Springer Verlag, 1987. | MR | Zbl

[4] Canny (J.). - Some algebraic and geometric computations in PS-PACE, ACM Symposium on the theory of computation, 1988, p. 460-467.

[5] Canny (J.). - The complexity of robot motion planning. - MIT Press, 1989.

[6] Collins (G.). - Quantifier elimination for real closed fields by cylindric algebraic decomposition, in Second GI Conference on Automata Theory and Formal Languages. - Lect. Notes in Comp. Sciences. - Springer-Verlag, Berlin, t. 33, 1975, p. 134-183. | MR | Zbl

[7] Caniglia (L.), Galligo (A.), Heintz (J.). - Some new effectivity bounds in computational geometry, Proc. AAECC-6 (Rome 1988), Best Paper Award AAECC-6. - Springer Lecture Notes in Computer Science, t. 357, p. 131-151. | MR | Zbl

[8] Coste (M.), Roy (M.-F.). - Thom's lemma, the coding of real algebraic numbers and the topology of semi-algebraic sets, J. of Symbolic Computation, t. 5, 1988, p. 121-129. | MR | Zbl

[9] Davenport (J.), Heintz (J.). - Real quantifier elimination is doubly exponential, J. of Symbolic Computation, t. 5, 1988, p. 29-35. | MR | Zbl

[10] Fitchas (N.), Galligo (A.), Morgenstern (J.). - Algorithmes rapides en séquentiel et en parallèle pour l'élimination des quantificateurs en géométrie élémentaire, Séminaire Structures Ordonnées, U.E.R. de Math. Univ. Paris VII, 1987. Version finale à paraître aux Publications de l'Université de Paris VII (1990). | Zbl

[11] Fitchas (N.), Galligo (A.), Morgenstern (J.). - Precise sequential and parallel complexity bounds for the quantifier elimination of algebraically closed fields, à paraître dans Journal of Pure and Applied Algebra. | Zbl

[12] Von Zur Gathen (J.). - Parallel arithmetic computations : a survey, Proc 13th Conf. MFCS, 1986. | MR | Zbl

[13] Gonzalez (L.), Lombardi (H.), Recio (T.), Roy (M.-F.). - Sturm-Habicht sequences, Proceedings ISSAC, ACM Press, 1989, p. 136-145.

[14] Gonzalez (L.), Lombardi (H.), Recio (T.), Roy (M.-F.). - Sous-résultants et spécialisation de la suite de Sturm, à paraître au RAIRO Informatique théorique.

[15] Grigor'Ev (D.). - Complexity of deciding Tarski algebra, J. Symbolic Computation, t. 5, 1988, p. 65-108. | MR | Zbl

[16] Grigor'Ev (D.), Vorobjov (N.). - Solving systems of polynomial inequalities in subexponential time, J. Symbolic Computation, t. 5, 1988, p. 37-64. | MR | Zbl

[17] Heintz (J.). - Definability and fast quantifier elimination in algebraically closed fields, Theor. Comput. Sci., t. 24, 1983, p. 239-277. | MR | Zbl

[18] Heintz (J.), Roy (M.-F.), Solernó (P.). - On the complexity of semialgebraic sets, Proc. IFIP (San Francisco, 1989), North Holland, 1989, p. 293-298.

[19] Heintz (J.), Roy (M.-F.), Solerno (P.). - Complexité du principe de Tarski-Seidenberg, C.R.A.S. Paris, t. 309, 1989, p. 825-830. | MR | Zbl

[20] Kobayashi (H.), Moritsugu (S.), Hogan (R.W.). - On solving systems of algebraic equations, soumis au Journal of Symbolic Computation.

[21] Krick (T.), Logar (A.). - Membership problems, representations and the computation of the radical of one-dimensional ideals, à paraître dans les Actes de MEGA, 1990.

[22] Loos (R.). - Generalized poynomial reaminder sequences, in Computer Algebra, Symbolic and Algebraic Computation. - Ed. Buchberger, Collins, Loos, Springer Verlag, 1982, p. 115-138. | Zbl

[23] Renegar (J.). - A faster PSPACE algorithm for deciding the existential theory of the reals, Technical Report 792, Cornell University Ithaca, 1988.

[24] Renegar (J.). - On the computational complexity and geometry of the first order theory of the reals, Technical Report 856, Cornell University Ithaca, 1989.

[25] Roy (M.-F.), Szpirglas (A.). - Complexity of computations with real algebraic numbers, à paraître au Journal of Symbolic Computation.

[26] Seidenberg (A.). - A new decision method for elementary algebra and geometry, Ann. Math., t. 60, 1954, p. 365-374. | MR | Zbl

[27] Shafarevitch (I.S.). - Algebraic geometry. - Springer Verlag, 1974.

[28] Solernó (P.). - Complejidad de conjuntos semialgebraicos, Thèse, Université de Buenos Aires, 1989.

[29] Sturm (C.). - Mémoire sur la résolution des équations numériques, Ins. France Sc. Math. Phys., t. 6, 1835.

[30] Sylvester (J.T.). - On a theory of syzygetic relations of two rational integral functions, comprising an application to the theory of Sturm's function, Trans. Roy. Soc. London (1853), reprint in Sylvester, Collected Math Papers, Chelsea Pub. Comp. N.Y., vol. 1, 1983, p. 429-586.

[31] Tarski (A.). - A decision method for elementary algebra and geometry. - Berkeley, 1951. | MR | Zbl

[32] Vorobjov (N.). - Bounds of real roots of a system of algebraic equations, Notes of Sci. Seminars of Leningrad Department of Math. Steklov Inst., t. 13, p. 7-19.

[33] Walker (R.). - Algebraic curves. - Princeton University Press, 1950. | MR | Zbl

[34] Weipsfenning (V.). - The complexity of linear problems in fields, J. Symbolic Computation, t. 5, 1988, p. 3-27. | MR | Zbl