実閉体
つまり、問題の大きさを n とするとき、アルゴリズムの実行時間を上から評価するような冪の塔 2 2 ⋅ ⋅ ⋅ n {\textstyle 2^{2^{\,\cdot ^{\,\cdot ^{\,\cdot ^{\,n}}}}}} は存在しない。Davenport & Heintz (1988) は量限定子消去が実は(少なくとも)二重指数的であることを示した。つまり、Ω 漸近記法を用いれば、n 個の量限定子を持つ式の族 Φn で長さ O(n) のものと一定の次数が存在して、Φn に同値な量限定子を持たない任意の式が次数 2 かつ長さ 2 の多項式を必ず含む。Ben-Or, Kozen & Reif (1986) は実閉体の理論が EXPSPACE において(したがって二重指数時間で)決定可能であることを示した。
Basu and Roy (1996) は ∃x1, ..., ∃xk; P1(x1, ..., xk) ⋈ 0 ∧ ⋯ ∧ Ps(x1, ..., xk) ⋈ 0 なる式(ただし、⋈ は "<", ">", "=" の何れか)が真かを決定するためのよく振る舞うアルゴリズムで、算術演算 sd の複雑性に属するものが存在することを示した。実は実数の存在理論(英語版)は PSPACE で決定できる。
追加の函数記号(例えば正弦函数 sin や指数函数 exp)を加えて、理論の決定可能性を変更(英語版)することができる。
まだほかにも、実閉体の重要なモデル理論的性質として、それが弱 o-極小構造(英語版)を持つことが挙げられる。逆に、任意の弱 o-極小順序体は実閉でなければならない。