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!

$\endgroup$
  • 1
    $\begingroup$ The context is not quite clear. Are you taking about multivariate case? Over reals, integers, finite fields? $\endgroup$ – Max Alekseyev Mar 27 '16 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 '16 at 16:27
  • 1
    $\begingroup$ This question is somewhat answered in mathoverflow.net/questions/115608/sat-and-arithmetic-geometry/… $\endgroup$ – Benjamin Steinberg Mar 27 '16 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 '16 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 '16 at 17:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.