# Why is solving polynomial systems NP hard?

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?
• 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$. – Benjamin Steinberg Mar 27 '16 at 16:27