<p>The problem is complete for the existential theory of the reals (<span class="math-container">$\exists\mathbb{R}$</span>). 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 <span class="math-container">$\exists\mathbb{R}$</span> see <a href="https://en.wikipedia.org/wiki/Existential_theory_of_the_reals" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Existential_theory_of_the_reals</a>). In comparison, the exact version is complete for the existential theory of the rationals (<span class="math-container">$\exists\mathbb{Q}$</span>), more or less by definition. <span class="math-container">$\exists\mathbb{Q}$</span> is at least as hard as <span class="math-container">$\exists\mathbb{R}$</span>, but not known to be decidable.</p>
<p>Sketch of proof that the approximate version of the problem is <span class="math-container">$\exists\mathbb{R}$</span>-hard for <span class="math-container">$\varepsilon = 1$</span>:</p>
<ol>
<li>Since the solution set is open, we can change the quantifiers to range over <span class="math-container">$\mathbb{R}$</span> rather than <span class="math-container">$\mathbb{Q}$</span>; this change leads to a logically equivalent formula.</li>
<li>Testing whether a polynomial <span class="math-container">$p(x)$</span> has a real (exact) solution <span class="math-container">$x\in \mathbb{R}^n$</span> inside the unit ball is <span class="math-container">$\exists\mathbb{R}$</span>-complete (this can be shown somewhat like Theorem 5.1 in <a href="https://link.springer.com/article/10.1007/s00224-015-9662-0" rel="nofollow noreferrer">https://link.springer.com/article/10.1007/s00224-015-9662-0</a>).</li>
<li>Testing <span class="math-container">$p(x) = 0$</span> for <span class="math-container">$\Vert x \Vert &lt; 1$</span> is equivalent to <span class="math-container">$|p(x)| &lt; 2^{-2^m}$</span> for some <span class="math-container">$\Vert x \Vert &lt; 1$</span>, where <span class="math-container">$m$</span> is (roughly) the description length of <span class="math-container">$p$</span> (the number of bits needed to write down <span class="math-container">$p$</span>). E.g. see Corollary 3.4 in the paper referenced above in (2).</li>
<li>This is then equivalent to <span class="math-container">$2^{2^m}|p(x)| &lt; 1$</span> for some <span class="math-container">$\Vert x \Vert &lt; 1$</span>. Assuming we can compute <span class="math-container">$c &gt; 2^{2^m}$</span>, the remaining conditions can all be expressed using polynomial conditions of the form <span class="math-container">$&lt;1$</span>.</li>
<li>We are left with showing that we can compute a number <span class="math-container">$c &gt; 2^{2^{m}}$</span> using polynomial conditions of the form allowed. We do this using repeated squaring and adding new variables. E.g. <span class="math-container">$|y_1-3|&lt;1$</span>, <span class="math-container">$|y_2-(y_1^2+1)| &lt; 1$</span>, etc. Then <span class="math-container">$y_i &gt; 2^{2^i}$</span>, so <span class="math-container">$m$</span> such equations are sufficient to build the constant we need.</li>
</ol>

CC BY-SA 4.0
2022-04-07T16:45:44.067Z
2022-04-07T16:45:44.067Z
user66277
<p>Consider the following problem:</p>
<p><strong>Input:</strong> <span class="math-container">$(p_1,...,p_n, \epsilon)$</span> where each <span class="math-container">$p_i$</span> is a polynomial in <span class="math-container">$m$</span> variables with integer coefficients and <span class="math-container">$\epsilon&gt;0$</span>.</p>
<p><strong>Output:</strong> If there is <span class="math-container">$(r_1,...,r_m) \in \mathbb{Q}^m$</span> such that <span class="math-container">$|p_i(r_1,...,r_m)|&lt;\epsilon$</span> for all <span class="math-container">$i$</span>, then output such a tuple. Otherwise, output None.</p>
<p><strong>My question:</strong> What's known about the complexity of this problem?</p>
<p>It's well known that the above problem is difficult when we ask for exact solutions.</p>

CC BY-SA 4.0
2022-04-05T21:14:02.913Z
Seems easy to show NP-hard, using a variant of a standard reduction from 3-SAT.
Neal Young
CC BY-SA 4.0
2022-04-05T22:00:25.033Z
@NealYoung Can you please sketch the reduction (or point to a reference)? That would be very helpful.
Haim
CC BY-SA 4.0
2022-04-06T15:14:32.203Z
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.
Tassle
CC BY-SA 4.0
2022-04-06T17:22:38.567Z
@Tassle Thanks! You might want to write it as an answer for the benefit of other people who might wonder about this question.
Haim
CC BY-SA 4.0
2022-04-07T02:29:50.507Z
(Or just $100|(1-r_1)(1-r_2)(1-r_3)| < 1$ to encode the clause.)
Neal Young
<cc.complexity-theory><polynomials><algebra>
Complexity of finding approximate solutions for systems of polynomial equations
Haim
# Complexity of finding approximate solutions for systems of polynomial equations

(Asked by: username_0 on 2022-04-05)

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.

**Tags:** cc.complexity-theory, polynomials, algebra

> **Comments:**
> **username_1**: Seems easy to show NP-hard, using a variant of a standard reduction from 3-SAT.  
> **username_0**: @NealYoung Can you please sketch the reduction (or point to a reference)? That would be very helpful.  
> **username_2**: 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.  
> **username_0**: @username_2 Thanks! You might want to write it as an answer for the benefit of other people who might wonder about this question.  
> **username_1**: (Or just $100|(1-r_1)(1-r_2)(1-r_3)| < 1$ to encode the clause.)  

---

## 1 answers

### Answer by username_3 on 2022-04-07. Score: 3 | Accepted answer

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.


---

