# Complexity of finding approximate solutions for systems of polynomial equations

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.

• Seems easy to show NP-hard, using a variant of a standard reduction from 3-SAT. Apr 5, 2022 at 21:14
• @NealYoung Can you please sketch the reduction (or point to a reference)? That would be very helpful.
– Haim
Apr 5, 2022 at 22:00
• You can easily force your variable $r_i$ to take values close to $0$ or $1$ via the condition $|100\cdot r_i(1-r_i)| < 2$. Then a clause $(v_1 \vee v_2 \vee v_3)$ can be encoded as $|(r_1+r_2+r_3-1)(r_1+r_2+r_3-2)(r_1+r_2+r_3-3)| < 2$ for example. Apr 6, 2022 at 15:14
• @Tassle Thanks! You might want to write it as an answer for the benefit of other people who might wonder about this question.
– Haim
Apr 6, 2022 at 17:22
• (Or just $100|(1-r_1)(1-r_2)(1-r_3)| < 1$ to encode the clause.) Apr 7, 2022 at 2:29

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.