7
$\begingroup$

Solving polynomial systems is known to be a NP hard problem; however it is not completely clear to me where this complexity comes from.

My interest is in the case of systems of multivariate polynomials over the real field.

Intuitively, I can imagine that part of the problem consists in the counting of the roots of the system: Bezout bound states that the number of roots is bounded by the product of the degrees of the polynomials composing the system; so if we have $n$ polynomials of degree 2, we will have at most $2^n $ solutions, so, if $t$ is the time needed to compute a solution, we should perform at most

$$ t2^n $$

operations. My question is:

  1. What can be said about t , the complexity of calculating a single solution?
  2. Is still a NP hard problem to solve non linear polynomial systems that are known to have only one solution?
  3. Is there any literature about this topic, studying the complexity of solving polynomial systems?

thanks!

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ The context is not quite clear. Are you taking about multivariate case? Over reals, integers, finite fields? $\endgroup$
    – Max Alekseyev
    Mar 27, 2016 at 16:01
  • 6
    $\begingroup$ You can encode 3-sat. The idea is equations $x^2-x=0$ make x Boolean valued and now encode intersection by product and complement by $1-x$. $\endgroup$
    – Benjamin Steinberg
    Mar 27, 2016 at 16:27
  • 1
    $\begingroup$ This question is somewhat answered in mathoverflow.net/questions/115608/sat-and-arithmetic-geometry/… $\endgroup$
    – Benjamin Steinberg
    Mar 27, 2016 at 16:35
  • 1
    $\begingroup$ I would expect things to not change too much; the problem of UNAMBIGUOUS_SAT (SAT where there's guaranteed at most one satisfying assignment) is still known to have complexity implications (namely NP=RP) if it's in P, and it shouldn't be hard to craft polynomial systems from there. $\endgroup$
    – Steven Stadnicki
    Mar 27, 2016 at 17:11
  • 1
    $\begingroup$ @ Steven Stadnick Actually, I am trying to solve a big system, described at high level here mathoverflow.net/questions/234254/… What I am experiencing is that most of the solvers spend a lot of time in counting the roots, while the time spent in calculating the various individual roots is much smaller. From this, I am trying to understand if it makes sense to modify the existing methods to make them calculate only one root, or if this is a lost battle (ie the problem is NP hard). $\endgroup$
    – Ulderique Demoitre
    Mar 27, 2016 at 17:25

0

Reset to default

Your Answer

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