Complexity of finding approximate solutions for systems of polynomial equations

Question

Consider the following problem:

Input: $(p_1,...,p_n, \epsilon)$ where each $p_i$ is a polynomial in $m$ variables with integer coefficients and $\epsilon>0$.

Output: If there is $(r_1,...,r_m) \in \mathbb{Q}^m$ such that $|p_i(r_1,...,r_m)|<\epsilon$ for all $i$, then output such a tuple. Otherwise, output None.

My question: What's known about the complexity of this problem?

It's well known that the above problem is difficult when we ask for exact solutions.

Answer 1

The problem is complete for the existential theory of the reals ($\exists\mathbb{R}$). This implies that the problem is NP-hard and can be decided in PSPACE, and there are consequences for the precision of a solution (for more info on $\exists\mathbb{R}$ see https://en.wikipedia.org/wiki/Existential_theory_of_the_reals). In comparison, the exact version is complete for the existential theory of the rationals ($\exists\mathbb{Q}$), more or less by definition. $\exists\mathbb{Q}$ is at least as hard as $\exists\mathbb{R}$, but not known to be decidable.

Sketch of proof that the approximate version of the problem is $\exists\mathbb{R}$-hard for $\varepsilon = 1$:

1. Since the solution set is open, we can change the quantifiers to range over $\mathbb{R}$ rather than $\mathbb{Q}$; this change leads to a logically equivalent formula.
2. Testing whether a polynomial $p(x)$ has a real (exact) solution $x\in \mathbb{R}^n$ inside the unit ball is $\exists\mathbb{R}$-complete (this can be shown somewhat like Theorem 5.1 in https://link.springer.com/article/10.1007/s00224-015-9662-0).
3. Testing $p(x) = 0$ for $\Vert x \Vert < 1$ is equivalent to $|p(x)| < 2^{-2^m}$ for some $\Vert x \Vert < 1$, where $m$ is (roughly) the description length of $p$ (the number of bits needed to write down $p$). E.g. see Corollary 3.4 in the paper referenced above in (2).
4. This is then equivalent to $2^{2^m}|p(x)| < 1$ for some $\Vert x \Vert < 1$. Assuming we can compute $c > 2^{2^m}$, the remaining conditions can all be expressed using polynomial conditions of the form $<1$.
5. We are left with showing that we can compute a number $c > 2^{2^{m}}$ using polynomial conditions of the form allowed. We do this using repeated squaring and adding new variables. E.g. $|y_1-3|<1$, $|y_2-(y_1^2+1)| < 1$, etc. Then $y_i > 2^{2^i}$, so $m$ such equations are sufficient to build the constant we need.