Аннотация:
Описан алгоритм, строящий по всякой формуле теории первого порядка алгебраически замкнутых полей эквивалентную ей бескванторную за время, полиномиальное от Ln2a+1, где L – размер формулы, n – число переменных, a – число перемен кванторов.
Библиография: 15 названий.
Образец цитирования:
Д. Ю. Григорьев, “Сложность разрешения теории первого порядка алгебраически замкнутых полей”, Изв. АН СССР. Сер. матем., 50:5 (1986), 1106–1120; Math. USSR-Izv., 29:2 (1987), 459–475
\RBibitem{Gri86}
\by Д.~Ю.~Григорьев
\paper Сложность разрешения теории первого порядка алгебраически замкнутых полей
\jour Изв. АН СССР. Сер. матем.
\yr 1986
\vol 50
\issue 5
\pages 1106--1120
\mathnet{http://mi.mathnet.ru/im1566}
\mathscinet{http://mathscinet.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}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/im1566
https://www.mathnet.ru/rus/im/v50/i5/p1106
Эта публикация цитируется в следующих 9 статьяx:
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
А. В. Селиверстов, “Кубические формы без мономов от двух переменных”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 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
Цитирование в формате AMSBIB
Обратная связь: