Geodesic
The complexity of the decision problem for the first order theory of algebraically closed fields
Izvestiya. Mathematics , Tome 29 (1987) no. 2, pp. 459-475.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{IM2_1987_29_2_a9,
     author = {D. Yu. Grigor'ev},
     title = {The complexity of the decision problem for the first order theory of algebraically closed fields},
     journal = {Izvestiya. Mathematics },
     pages = {459--475},
     publisher = {mathdoc},
     volume = {29},
     number = {2},
     year = {1987},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_1987_29_2_a9/}
}
TY  - JOUR
AU  - D. Yu. Grigor'ev
TI  - The complexity of the decision problem for the first order theory of algebraically closed fields
JO  - Izvestiya. Mathematics 
PY  - 1987
SP  - 459
EP  - 475
VL  - 29
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_1987_29_2_a9/
LA  - en
ID  - IM2_1987_29_2_a9
ER  - 
%0 Journal Article
%A D. Yu. Grigor'ev
%T The complexity of the decision problem for the first order theory of algebraically closed fields
%J Izvestiya. Mathematics 
%D 1987
%P 459-475
%V 29
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_1987_29_2_a9/
%G en
%F IM2_1987_29_2_a9
D. Yu. Grigor'ev. The complexity of the decision problem for the first order theory of algebraically closed fields. Izvestiya. Mathematics , Tome 29 (1987) no. 2, pp. 459-475. http://geodesic.mathdoc.fr/item/IM2_1987_29_2_a9/

[1] Tarski A., A decision method for elementary algebra and geometry, Berkeley, 1951

[2] Akho A., Khopkroft D., Ulman D., Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979 | MR | Zbl

[3] Slisenko A. O., “Slozhnostnye zadachi teorii vychislenii”, Uspekhi matem. nauk, 36:6 (1981), 21–103 | MR | Zbl

[4] Seidenberg A., “Constructions in algebra”, Trans. Amer. Math. Soc., 197 (1974), 273–313 | DOI | MR | Zbl

[5] Collins G. E., “Quantifier elimination for real closed fields by cylindrical algebraic decomposition”, Lect. Notes Comput. Sci., 33 (1975), 134–183 | MR | Zbl

[6] Wüthrich H. R., “Ein Entscheidungsverfahren für die Theorie der reellabgeschlossenen Körper”, Lect. Notes Comput. Sci., 43 (1976), 138–162 | Zbl

[7] Heintz J., Definability and fast quantifier elimination in algebraically closed fields, Preprint University Frankfurt, West Germany, December, 1981 | MR

[8] Fischer M. J., Rabin M. O., “Super-exponential complexity of Presburger arithmetic”, Complexity of Computations (SIAM-AMS Proc., 7), Providence, R. J., 1974, 27–41 | MR | Zbl

[9] Grigorev D. Yu., “Razlozhenie mnogochlenov nad konechnym polem i reshenie sistem algebraicheskikh uravnenii”, Zap. nauchn. seminarov LOMI, 137, 1984, 20–79 | MR

[10] Chistov A. L., “Algoritm polinomialnoi slozhnosti dlya razlozheniya mnogochlenov i nakhozhdenie komponent mnogoobraziya v subeksponentsialnoe vremya”, Zap. nauchn. seminarov LOMI, 137, 1984, 124–188 | MR | Zbl

[11] Zarisskii O., Samyuel P., Kommutativnaya algebra, t. 1,2, IL, M., 1963

[12] Lazard D., “Resolution des systemes d'equations algebriques”, Theor. Comput. Sci., 15 (1981), 77–110 | DOI | MR | Zbl

[13] Grigorev D. Yu., “Sootnoshenie ranga i multiplikativnoi slozhnosti bilineinoi formy nad neterovym kommutativnym koltsom”, Zap. nauchn. seminarov LOMI, 86, 1979, 66–81 | MR

[14] Shafarevich I. R., Osnovaniya algebraicheskoi geometrii, Nauka, M., 1972 | MR | Zbl

[15] Gantmakher F. R., Teoriya matrits, Nauka, M., 1967 | MR