<p>Yes, even in the purely existential case. See <a href="https://en.wikipedia.org/wiki/Existential_theory_of_the_reals" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Existential_theory_of_the_reals</a></p>

CC BY-SA 4.0
2019-12-21T07:45:48.593Z
... and this holds for any first-order theory that admits some model with at least two elements, not just for the real field.
Emil Jeřábek
CC BY-SA 4.0
2019-12-21T11:42:28.667Z
Sorry, this isn't quite right. If a consistent theory T *proves* the existence of at least two elements, the existential theory of T is NP-hard. If a theory T is only *consistent* with the existence of at least two elements, then satisfiability of existential sentences in a model of T is NP-hard, or in other words, the universal theory of T is coNP-hard.
Emil Jeřábek
CC BY-SA 4.0
2019-12-21T07:32:30.440Z
2019-12-21T07:32:30.440Z
David Eppstein
<p>The decision procedure of theory of closed real field  refers to <a href="https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers</a></p>

<cc.complexity-theory><np-hardness><complexity-classes><computational-geometry>
The decision procedure of theory of closed real field is in NP-hard?
XL _At_Here_There
# The decision procedure of theory of closed real field is in NP-hard?

(Asked by: username_0 on 2019-12-21)

The decision procedure of theory of closed real field refers to <https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers>

**Tags:** cc.complexity-theory, np-hardness, complexity-classes, computational-geometry

---

## 1 answers

### Answer by username_1 on 2019-12-21. Score: 3 | Accepted answer

Yes, even in the purely existential case. See <https://en.wikipedia.org/wiki/Existential_theory_of_the_reals>

> **Comments:**
> **username_2**: ... and this holds for any first-order theory that admits some model with at least two elements, not just for the real field.  
> **username_2**: Sorry, this isn't quite right. If a consistent theory T *proves* the existence of at least two elements, the existential theory of T is NP-hard. If a theory T is only *consistent* with the existence of at least two elements, then satisfiability of existential sentences in a model of T is NP-hard, or in other words, the universal theory of T is coNP-hard.  

---

