RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Izv. RAN. Ser. Mat.: Year: Volume: Issue: Page: Find

 Personal entry: Login: Password: Save password Enter Forgotten password? Register

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

This article is cited in 5 scientific papers (total in 5 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.

Full text: PDF file (1775 kB)
References: PDF file   HTML file

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

Bibliographic databases:

UDC: 518.5
MSC: Primary 68Q40; Secondary 03C10, 12L99
Received: 25.07.1984

Citation: D. Yu. Grigor'ev, “The complexity of the decision problem for the first order theory of algebraically closed fields”, Izv. Akad. Nauk SSSR Ser. Mat., 50:5 (1986), 1106–1120; Math. USSR-Izv., 29:2 (1987), 459–475

Citation in format AMSBIB
\Bibitem{Gri86} \by D.~Yu.~Grigor'ev \paper The complexity of the decision problem for the first order theory of algebraically closed fields \jour Izv. Akad. Nauk SSSR Ser. Mat. \yr 1986 \vol 50 \issue 5 \pages 1106--1120 \mathnet{http://mi.mathnet.ru/izv1566} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=873663} \zmath{https://zbmath.org/?q=an:0631.03006|0625.03004} \transl \jour Math. USSR-Izv. \yr 1987 \vol 29 \issue 2 \pages 459--475 \crossref{https://doi.org/10.1070/IM1987v029n02ABEH000979} 

Linking options:
• http://mi.mathnet.ru/eng/izv1566
• http://mi.mathnet.ru/eng/izv/v50/i5/p1106

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Noaï Fitchas, André 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
2. 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
3. Gregorio Malajovich, Klaus Meer, “On the Structure of $\cal NP_\Bbb C$”, SIAM J Comput, 28:1 (1998), 27
4. 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
5. A. V. Seliverstov, “Kubicheskie formy bez monomov ot dvukh peremennykh”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 25:1 (2015), 71–77
•  Number of views: This page: 267 Full text: 56 References: 30 First page: 1

 Contact us: math-net2019_11 [at] mi-ras ru Terms of Use Registration Logotypes © Steklov Mathematical Institute RAS, 2019