2
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Seems easy to show NP-hard, using a variant of a standard reduction from 3-SAT. $\endgroup$
    – Neal Young
    Apr 5, 2022 at 21:14
  • $\begingroup$ @NealYoung Can you please sketch the reduction (or point to a reference)? That would be very helpful. $\endgroup$
    – Haim
    Apr 5, 2022 at 22:00
  • $\begingroup$ 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. $\endgroup$
    – Tassle
    Apr 6, 2022 at 15:14
  • 1
    $\begingroup$ @Tassle Thanks! You might want to write it as an answer for the benefit of other people who might wonder about this question. $\endgroup$
    – Haim
    Apr 6, 2022 at 17:22
  • $\begingroup$ (Or just $100|(1-r_1)(1-r_2)(1-r_3)| < 1$ to encode the clause.) $\endgroup$
    – Neal Young
    Apr 7, 2022 at 2:29

1 Answer 1

3
$\begingroup$

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.
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.