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:
- What can be said about t , the complexity of calculating a single solution?
- Is still a NP hard problem to solve non linear polynomial systems that are known to have only one solution?
- Is there any literature about this topic, studying the complexity of solving polynomial systems?