Given a system of 2nd-degree polynomials, $P=\{p\_1,\dots,p\_m\}$ where $p\_i: \mathbb{R}^n \rightarrow \mathbb{R}$, can you efficiently find a common zero of all of these polynomials? In other words, given $P$, can you find $x\_1,\dots,x\_n\in\mathbb{R}$ such that $p\_i(x\_1,\dots,x\_n)=0$ for all $i$? I only need to find one solution.


I know that in the general case (arbitrary degree polynomials) this can't be done efficiently. However, I'm wondering if there are any good techniques in the quadratic case, specifically if there is a polynomial time solution.



Can you efficiently solve a system of quadratic multivariate polynomials?
There is an exact algorithm that needs $n^{O(m)}$ operations (cf. <http://arxiv.org/abs/cs/0403008>). One cannot expect anything better than that, unless P=NP. Indeed, it is easy to formulate several NP-complete problems as testing solvability of linear equations in 0-1 variables $x\_i$, and the latter can be enforced by quadratic equations $x^2\_i-x\_i=0$. 


