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.
$\begingroup$
$\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$– Emil JeřábekCommented Jan 13, 2021 at 10:37
Add a comment
|