I know that in the general case it isn't efficient. However, I'm wondering if there are any good techniques in the quadratic case over the reals, specifically if there is a polynomial time solution.
What are some efficient algorithms for determining if a system of quadratic multivariate polynomials have a solution?
cc.complexity theory;polynomials;polynomial time;quadratic
This problem is NP-hard, as can be shown by a straightforward reduction from SAT.It sounds like you are interested in the case of $m$ quadratic equations on $n$ variables (over $\mathbb{R}$).  In practice, the hardness of this problem depends on the relationship between $m$ and $n$:If $m = \Theta(n)$, this problem is believed to be very hard (say, exponential in $n$).If $m \ge n^2/2$ (roughly), this problem is easy and can be solved through linearization: replace each quadratic monomial $x_i x_j$ with a new variable $t_{i,j}$, then use Gaussian elimination.If $m = \Theta(n^2)$, this problem can be solved in polynomial time through relinearization.  Roughly speaking, you linearize as above; then, for each $i,j,k,l$, you add constraints $t_{i,j} t_{k,l} = t_{i,k} t_{j,l} = t_{i,l} t_{j,k}$, which are themselves quadratic equations.  This gives you a new system of quadratic equations in the variables $x_i$, $t_{i,j}$.  Now you can apply linearization (or recursively apply relinearization) to this system of quadratic equations.  For details, see my explanation elsewhere and the reference into the literature there: https://crypto.stackexchange.com/a/3736/351If $m = \omega(n)$ and $m = o(n^2)$, I don't know what the complexity is.There are also Grobner basis algorithms, the XL and XSL algorithms, and probably others as well.  I don't know if there are any provable, useful running time bounds for any of them for any useful parameter ranges.Incidentally, you probably don't want to work over the real numbers (where even testing equality is hard), but over the rationals or the integers or some finite field.