RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. 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)}$.

UDC: 519.5+512.46


 English version:
Journal of Soviet Mathematics, 1991, 55:2, 1553–1587

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025