|
Zapiski Nauchnykh Seminarov LOMI, 1988, Volume 174, Pages 53–100
(Mi znsl4512)
|
|
|
|
Complexity of deciding the first-order theory of real closed fields
D. Yu. Grigor'ev
Abstract:
Let a formula with $a$ quantifier alternations be given having atomic subformulas of the kind ($f_j\geqslant0$) with polynomials $f_i$ as in [5]. Deciding algorithm is designed with complexity $(M(kd)^{(O(n))^{5a-2(m+1)}}\cdot d_0^{(m+n)})^{O(1)}$.
Citation:
D. Yu. Grigor'ev, “Complexity of deciding the first-order theory of real closed fields”, Computational complexity theory. Part 3, Zap. Nauchn. Sem. LOMI, 174, "Nauka", Leningrad. Otdel., Leningrad, 1988, 53–100; J. Soviet Math., 55:2 (1991), 1553–1587
Linking options:
https://www.mathnet.ru/eng/znsl4512 https://www.mathnet.ru/eng/znsl/v174/p53
|
|