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:
Citation in format AMSBIB
Contact us: