×

zbMATH — the first resource for mathematics

On the complexity of the Tarski-Seidenberg principle. (Sur la complexité du principe de Tarski-Seidenberg.) (French) Zbl 0767.03017
Summary: This paper is devoted to an algorithm for quantifier elimination in the real closed case which is of simple exponential complexity in the number of variables in the sequential model (and polynomial in the parallel model) as soon as the number of alternations of quantifiers is fixed.

MSC:
03C10 Quantifier elimination, model completeness, and related topics
14G25 Global ground fields in algebraic geometry
68Q25 Analysis of algorithms and problem complexity
03C60 Model-theoretic algebra
12L12 Model theory of fields
PDF BibTeX Cite
Full Text: DOI Numdam EuDML
References:
[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 87m:03056 | Zbl 0634.03031 · Zbl 0634.03031
[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 85k:65111 | Zbl 0541.68019 · Zbl 0541.68019
[3] BOCHNAK (J.) , COSTE (M.) , ROY (M.-F.) . - Géométrie algébrique réelle . - Springer Verlag, 1987 . MR 90b:14030 | Zbl 0633.14016 · Zbl 0633.14016
[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 53 #7771 | Zbl 0318.02051 · Zbl 0318.02051
[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 90j:13001 | Zbl 0685.68044 · Zbl 0685.68044
[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 89g:12002 | Zbl 0689.14006 · Zbl 0689.14006
[9] DAVENPORT (J.) , HEINTZ (J.) . - Real quantifier elimination is doubly exponential , J. of Symbolic Computation, t. 5, 1988 , p. 29-35. MR 89g:03009 | Zbl 0663.03015 · Zbl 0663.03015
[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 0704.03014 · Zbl 0704.03014
[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 0716.03023 · Zbl 0716.03023
[12] VON ZUR GATHEN (J.) . - Parallel arithmetic computations : a survey , Proc 13th Conf. MFCS, 1986 . MR 874591 | Zbl 0616.68037 · Zbl 0616.68037
[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. · Zbl 0732.68059
[15] GRIGOR’EV (D.) . - Complexity of deciding Tarski algebra , J. Symbolic Computation, t. 5, 1988 , p. 65-108. MR 90b:03054 | Zbl 0689.03021 · Zbl 0689.03021
[16] GRIGOR’EV (D.) , VOROBJOV (N.) . - Solving systems of polynomial inequalities in subexponential time , J. Symbolic Computation, t. 5, 1988 , p. 37-64. MR 89h:13001 | Zbl 0662.12001 · Zbl 0662.12001
[17] HEINTZ (J.) . - Definability and fast quantifier elimination in algebraically closed fields , Theor. Comput. Sci., t. 24, 1983 , p. 239-277. MR 85a:68062 | Zbl 0546.03017 · Zbl 0546.03017
[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 92c:12012 | Zbl 0704.03013 · Zbl 0704.03013
[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 0577.13001 · Zbl 0577.13001
[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. · Zbl 0718.14028
[26] SEIDENBERG (A.) . - A new decision method for elementary algebra and geometry , Ann. Math., t. 60, 1954 , p. 365-374. MR 16,209a | Zbl 0056.01804 · Zbl 0056.01804
[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 13,423a | Zbl 0044.25102 · Zbl 0044.25102
[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 11,387e | Zbl 0039.37701 · Zbl 0039.37701
[34] WEIPSFENNING (V.) . - The complexity of linear problems in fields , J. Symbolic Computation, t. 5, 1988 , p. 3-27. MR 89g:11123 | Zbl 0646.03005 · Zbl 0646.03005
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.