2
$\begingroup$

What is known about the complexity of deciding whether a finite set of polynomial inequalities in $n$ real variables with integer coefficients is satisfiable? Decidability is guaranteed by Tarski's theorem (see the answers to this related question), but his proof is nonconstructive and gives no complexity bound.

$\endgroup$
1
  • 8
    $\begingroup$ This computational problem is known as the existential theory of the reals. It sits somewhere between NP and PSPACE, but not much more is known; it’s important enough that it’s been given a complexity class of its own ($\exists\mathbb R$). (The official definition as in the Wikipedia article allows the arbitrary existential sentences, but this easily reduces to the case of satisfiability of a single polynomial equation by introduction of a few extension variables.) $\endgroup$ Jan 13, 2021 at 10:37

0

Your Answer

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