1
$\begingroup$

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

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ ... and this holds for any first-order theory that admits some model with at least two elements, not just for the real field. $\endgroup$ Dec 21, 2019 at 7:45
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 21, 2019 at 11:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.