2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Shaull
    Jun 25, 2021 at 17:56
  • $\begingroup$ @Shaull I have edited the question to include what I can. $\endgroup$
    – Ken Robbins
    Jun 25, 2021 at 18:05
  • 1
    $\begingroup$ 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? $\endgroup$
    – Peter Shor
    Jun 28, 2021 at 1:07
  • 1
    $\begingroup$ @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\}$. $\endgroup$
    – Ken Robbins
    Jun 28, 2021 at 17:41
  • $\begingroup$ @KenRobbins: that's what I thought you meant; I just wanted to be sure. $\endgroup$
    – Peter Shor
    Jun 28, 2021 at 18:18

3 Answers 3

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Can we do a reduction to the case of polynomials with the promise that there is at least one real root? $\endgroup$
    – Kaveh
    Jun 28, 2021 at 0:21
0
$\begingroup$

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".

Improve this answer
$\endgroup$
4
  • $\begingroup$ Are you sure this holds for multivariate polynomials? They can have exponentially many roots. $\endgroup$
    – Shaull
    Jun 26, 2021 at 11:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Jun 26, 2021 at 16:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Jun 27, 2021 at 10:56
  • $\begingroup$ @Peter, that sounds right to me. Maybe post it as an answer? $\endgroup$
    – Kaveh
    Jun 27, 2021 at 13:25

Your Answer

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

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