Abstract:
An algorithm is described that constructs, from every formula of the first order theory of algebraically closed fields, an equivalent quantifier-free formula in time which is polynomial in $\mathscr L^{n^{2a+1}}$, where $\mathscr L$ is the size of the formula, $n$ is the number of variables, and $a$ is the number of changes of quantifiers.
Bibliography: 15 titles.
Citation:
D. Yu. Grigor'ev, “The complexity of the decision problem for the first order theory of algebraically closed fields”, Math. USSR-Izv., 29:2 (1987), 459–475
\Bibitem{Gri86}
\by D.~Yu.~Grigor'ev
\paper The complexity of the decision problem for the first order theory of algebraically closed fields
\jour Math. USSR-Izv.
\yr 1987
\vol 29
\issue 2
\pages 459--475
\mathnet{http://mi.mathnet.ru/eng/im1566}
\crossref{https://doi.org/10.1070/IM1987v029n02ABEH000979}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=873663}
\zmath{https://zbmath.org/?q=an:0631.03006|0625.03004}
Linking options:
https://www.mathnet.ru/eng/im1566
https://doi.org/10.1070/IM1987v029n02ABEH000979
https://www.mathnet.ru/eng/im/v50/i5/p1106
This publication is cited in the following 9 articles:
Hamid Rahkooy, Thomas Sturm, Lecture Notes in Computer Science, 12291, Computer Algebra in Scientific Computing, 2020, 510
V. A. Lyubetsky, A. V. Seliverstov, “A novel algorithm for solution of a combinatory set partitioning problem”, J. Commun. Technol. Electron., 61:6 (2016), 705
A. V. Seliverstov, “Kubicheskie formy bez monomov ot dvukh peremennykh”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 25:1 (2015), 71–77
Gregorio Malajovich, Klaus Meer, “On the Structure of $\cal NP_\Bbb C$”, SIAM J Comput, 28:1 (1998), 27
Susana Puddu, Juan Sabia, “An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs”, Journal of Pure and Applied Algebra, 129:2 (1998), 173
James Renegar, “On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals”, Journal of Symbolic Computation, 13:3 (1992), 255
Noaï Fitchas, André Galligo, Jacques Morgenstern, “Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields”, Journal of Pure and Applied Algebra, 67:1 (1990), 1
Volker STRASSEN, Algorithms and Complexity, 1990, 633
Citation in format AMSBIB
Contact us: