RUS  ENG
Full version
JOURNALS // Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya // Archive

Izv. Akad. Nauk SSSR Ser. Mat., 1986 Volume 50, Issue 5, Pages 1106–1120 (Mi im1566)

This article is cited in 9 papers

The complexity of the decision problem for the first order theory of algebraically closed fields

D. Yu. Grigor'ev


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.

UDC: 518.5

MSC: Primary 68Q40; Secondary 03C10, 12L99

Received: 25.07.1984


 English version:
Mathematics of the USSR-Izvestiya, 1987, 29:2, 459–475

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024