<p>If the coefficients are roots of rational numbers, then they are in particular algebraic numbers. This means that you can encode the coefficients as additional polynomial constraints.
So overall, you're looking at a system of Diophantine equations (i.e., polynomials with integer coefficients).</p>
<p>The sets defined by such equations are known as algebraic varieties (and if you have inequalities -- semialgebraic sets).</p>
<p>There are several ways of finding points within the solution set of such a system. One general approach is to use Cylindrical Algebraic Decomposition (CAD), but its complexity is quite bad.</p>
<p>The problem can be solved (to my knowledge) in single-exponential time. See e.g., <a href="https://core.ac.uk/download/pdf/82147919.pdf" rel="noreferrer">https://core.ac.uk/download/pdf/82147919.pdf</a></p>
<p>Note that by ``solving'' I mean finding the description of an algebraic point within the set of solutions. Then, approximating it to <span class="math-container">$\epsilon$</span> accuracy can be easily done using standard evaluation algorithms for algebraic numbers.</p>

CC BY-SA 4.0
2021-06-25T19:05:10.353Z
2021-06-25T19:05:10.353Z
Shaull
<p>The problem is NP-hard. If you have <span class="math-container">$P$</span> polynomials, you can use them to encode 1-in-3 SAT.</p>
<p>Take an instance of 1-in-3 SAT. First, take the equations <span class="math-container">$x_i^2 = 1$</span> for each variable. This means all the variables must be either <span class="math-container">$\pm1$</span>, ensuring that all solutions are real. Now, for all clause add the equation <span class="math-container">$x_i+x_j+x_k = -1$</span>, where the clause contains variables <span class="math-container">$x_i$</span>, <span class="math-container">$x_j$</span>, and <span class="math-container">$x_k$</span>. Now, every clause must contain exactly one <span class="math-container">$+1$</span> variable, which means there is a zero (or near-zero) of the polynomial if and only if there is a solution of the 1-in-3 SAT formula.</p>

CC BY-SA 4.0
2021-06-28T00:21:45.073Z
Can we do a reduction to the case of polynomials with the promise that there is at least one real root?
Kaveh
CC BY-SA 4.0
2021-06-27T13:30:14.837Z
2021-06-27T13:35:35.033Z
2021-06-27T13:35:35.033Z
Peter Shor 
<p>The answer below is incorrect.</p>
<p>The result about roots of polynomials is not for multivariate polynomials.</p>
<hr />
<p>If I am not mistaken, I think it is poly time.</p>
<p>First, note that you can turn it into a single polynomial equation by squaring and summing them.</p>
<p>Now finding the roots of a polynomial whose coefficients are poly time computable is poly time computable.</p>
<p>For details, see Ker-I Ko's book &quot;Complexity Theory of Real Functions&quot;.</p>

CC BY-SA 4.0
2021-06-26T11:12:04.627Z
Are you sure this holds for multivariate polynomials? They can have exponentially many roots.
Shaull
CC BY-SA 4.0
2021-06-26T16:44:53.460Z
We don't need to find all of them, however I am not sure the theorem applied to multivariate polynomials, so you are probably right.
Kaveh
CC BY-SA 4.0
2021-06-27T10:56:08.473Z
If you have $P$ polynomials, can't you use them to encode 1-in-3 SAT? First take all the equations $x_i^2=1$, so all the variables are either $-1$ or $1$. Then add the equations $x_i+x_j+x_k=-1$ for each clause. It's NP-hard.
Peter Shor 
CC BY-SA 4.0
2021-06-27T13:25:41.287Z
@Peter, that sounds right to me. Maybe post it as an answer?
Kaveh
CC BY-SA 4.0
2021-06-26T10:37:50.140Z
2021-06-27T13:29:38.137Z
2021-06-27T13:29:38.137Z
Kaveh
<p>Let there be a set of <span class="math-container">$P$</span> polynomial equations <span class="math-container">$f_j(x_1,x_2...x_V)=0$</span> where <span class="math-container">$1\leq j\leq P$</span>. For each <span class="math-container">$f_j$</span> the coefficients are real and every variable goes up to degree <span class="math-container">$D$</span>. It is also guaranteed that every root of every <span class="math-container">$f_j$</span> is guaranteed to be real.</p>
<p>If we want to numerically find a solution <span class="math-container">$\{X_1,X_2,..,X_V\}$</span> to the set of polynomials within accuracy <span class="math-container">$\varepsilon$</span>, what is the <span class="math-container">$\mathcal{O}()$</span> cost for this? What's the computational cost?</p>
<p>The coefficients are real, irrational but efficiently calculable. I'm not sure how specific I can get, but they're fractions and square-roots.</p>
<p>For some reason I'm having trouble finding this answer; my advisor seems to think it should be very easy to find. If possible I'd really like to find a source for the information as well.</p>

CC BY-SA 4.0
2021-06-25T17:56:16.080Z
When you say "the coefficients are real" - what do you know about them? Rationals? Algebraic? Efficiently computable? Effectively computable? This information would affect the solution.
Shaull
CC BY-SA 4.0
2021-06-25T18:05:41.407Z
@Shaull I have edited the question to include what I can.
Ken Robbins
CC BY-SA 4.0
2021-06-28T01:07:16.703Z
What do you mean "every root of every $f_j$ is real". Aren't these a set of simultaneous equations, and there are only a finite set of solutions if you consider them all at once?
Peter Shor 
CC BY-SA 4.0
2021-06-28T17:41:30.417Z
@PeterShor I am stumbling over my words. I mean that it's guaranteed that the solution $\{f_1(X_1,X_2...X_V)=0,f_2(X_1,X_2,...X_V)=0,...,f_P(X_1,X_2,...,X_V)=0\}$ etc can be found with entirely real values for $\{X_1, X_2, X_3...X_V\}$.
Ken Robbins
CC BY-SA 4.0
2021-06-28T18:18:40.950Z
@KenRobbins: that's what I thought you meant; I just wanted to be sure.
Peter Shor 
<cc.complexity-theory><polynomials><na.numerical-analysis>
Cost of Numerically Solving a System of P polynomials, each of V variables, and degree D to a Specific Accuracy
Ken Robbins
# Cost of Numerically Solving a System of P polynomials, each of V variables, and degree D to a Specific Accuracy

(Asked by: username_0 on 2021-06-25)

Let there be a set of $P$ polynomial equations $f\_j(x\_1,x\_2...x\_V)=0$ where $1\leq j\leq P$. For each $f\_j$ the coefficients are real and every variable goes up to degree $D$. It is also guaranteed that every root of every $f\_j$ is guaranteed to be real.

If we want to numerically find a solution $\{X\_1,X\_2,..,X\_V\}$ to the set of polynomials within accuracy $\varepsilon$, what is the $\mathcal{O}()$ cost for this? What's the computational cost?

The coefficients are real, irrational but efficiently calculable. I'm not sure how specific I can get, but they're fractions and square-roots.

For some reason I'm having trouble finding this answer; my advisor seems to think it should be very easy to find. If possible I'd really like to find a source for the information as well.

**Tags:** cc.complexity-theory, polynomials, na.numerical-analysis
> **Comments:**
> **username_1**: When you say "the coefficients are real" - what do you know about them? Rationals? Algebraic? Efficiently computable? Effectively computable? This information would affect the solution.  
> **username_0**: @Shaull I have edited the question to include what I can.  
> **username_2**: What do you mean "every root of every $f_j$ is real". Aren't these a set of simultaneous equations, and there are only a finite set of solutions if you consider them all at once?  
> **username_0**: @PeterShor I am stumbling over my words. I mean that it's guaranteed that the solution $\{f_1(X_1,X_2...X_V)=0,f_2(X_1,X_2,...X_V)=0,...,f_P(X_1,X_2,...,X_V)=0\}$ etc can be found with entirely real values for $\{X_1, X_2, X_3...X_V\}$.  
> **username_2**: @KenRobbins: that's what I thought you meant; I just wanted to be sure.  

---

## 3 answers

### Answer by username_1 on 2021-06-25. Score: 5 | Accepted answer

If the coefficients are roots of rational numbers, then they are in particular algebraic numbers. This means that you can encode the coefficients as additional polynomial constraints.
So overall, you're looking at a system of Diophantine equations (i.e., polynomials with integer coefficients).

The sets defined by such equations are known as algebraic varieties (and if you have inequalities -- semialgebraic sets).

There are several ways of finding points within the solution set of such a system. One general approach is to use Cylindrical Algebraic Decomposition (CAD), but its complexity is quite bad.

The problem can be solved (to my knowledge) in single-exponential time. See e.g., <https://core.ac.uk/download/pdf/82147919.pdf>

Note that by ``solving'' I mean finding the description of an algebraic point within the set of solutions. Then, approximating it to $\epsilon$ accuracy can be easily done using standard evaluation algorithms for algebraic numbers.


---

### Answer by username_2 on 2021-06-27. Score: 1

The problem is NP-hard. If you have $P$ polynomials, you can use them to encode 1-in-3 SAT.

Take an instance of 1-in-3 SAT. First, take the equations $x\_i^2 = 1$ for each variable. This means all the variables must be either $\pm1$, ensuring that all solutions are real. Now, for all clause add the equation $x\_i+x\_j+x\_k = -1$, where the clause contains variables $x\_i$, $x\_j$, and $x\_k$. Now, every clause must contain exactly one $+1$ variable, which means there is a zero (or near-zero) of the polynomial if and only if there is a solution of the 1-in-3 SAT formula.

> **Comments:**
> **username_3**: Can we do a reduction to the case of polynomials with the promise that there is at least one real root?  

---

### Answer by username_3 on 2021-06-26. Score: 0

The answer below is incorrect.

The result about roots of polynomials is not for multivariate polynomials.

---

If I am not mistaken, I think it is poly time.

First, note that you can turn it into a single polynomial equation by squaring and summing them.

Now finding the roots of a polynomial whose coefficients are poly time computable is poly time computable.

For details, see Ker-I Ko's book "Complexity Theory of Real Functions".

> **Comments:**
> **username_1**: Are you sure this holds for multivariate polynomials? They can have exponentially many roots.  
> **username_3**: We don't need to find all of them, however I am not sure the theorem applied to multivariate polynomials, so you are probably right.  
> **username_2**: If you have $P$ polynomials, can't you use them to encode 1-in-3 SAT? First take all the equations $x_i^2=1$, so all the variables are either $-1$ or $1$. Then add the equations $x_i+x_j+x_k=-1$ for each clause. It's NP-hard.  
> **username_3**: @Peter, that sounds right to me. Maybe post it as an answer?  

---

