<p>This problem is NP-hard, as can be shown by a straightforward reduction from SAT.</p>

<p>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$:</p>

<ul>
<li><p>If $m = \Theta(n)$, this problem is believed to be very hard (say, exponential in $n$).</p></li>
<li><p>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.</p></li>
<li><p>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: <a href="https://crypto.stackexchange.com/a/3736/351">https://crypto.stackexchange.com/a/3736/351</a></p></li>
<li><p>If $m = \omega(n)$ and $m = o(n^2)$, I don't know what the complexity is.</p></li>
</ul>

<p>There are also <a href="https://en.wikipedia.org/wiki/Gr%C3%B6bner_basis" rel="nofollow noreferrer">Grobner basis</a> algorithms, the <a href="https://en.wikipedia.org/wiki/XSL_attack" rel="nofollow noreferrer">XL and XSL algorithms</a>, 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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-01-04T04:00:25.170Z
2014-01-04T04:00:25.170Z
2017-04-13T12:48:17.970Z
D.W.
<p>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.</p>

CC BY-SA 3.0
2014-01-03T10:30:21.007Z
I may be missing something: What is the difference with [your previous question](http://cstheory.stackexchange.com/questions/20139/what-are-some-efficient-algorithms-for-finding-the-solutions-to-a-quadratic-mult) or [Nick's question](http://cstheory.stackexchange.com/questions/19832/what-are-some-efficient-algorithms-for-determining-if-a-quadratic-multivariate-p)?
Bruno
CC BY-SA 3.0
2014-01-03T18:58:30.170Z
@Bruno This is for a system of equations. Those other two are for just one polynomial.
Joe
CC BY-SA 3.0
2014-01-03T19:00:33.980Z
I thought a system of equations would be a different question. Why the downvotes? Should I change the meaning of my existing question instead of asking a new one?
Joe
CC BY-SA 3.0
2014-01-03T19:30:07.290Z
Ok for the difference. I just had the impress of a lot of very similar questions in a very short time. I would suggest that you give the variants of your question in the first of you question. I would be clearer I think.
Bruno
CC BY-SA 3.0
2014-01-04T03:53:10.393Z
Joe, I agree, this doesn't seem to be a duplicate of those prior questions.  However, people might have downvoted because your question didn't show any evidence of prior research.  (We expect you to do substantial research on your own before asking.)  Also, I recommend that you edit the question with the answers to questions asked over on those other threads, e.g. a rough estimate of the number of variables and of the number of polynomials.  If you're looking for a practical solution, this might make a big difference.
D.W.
<cc.complexity-theory><polynomials><polynomial-time><quadratic>
What are some efficient algorithms for determining if a system of quadratic multivariate polynomials have a solution?
Joe
# What are some efficient algorithms for determining if a system of quadratic multivariate polynomials have a solution?

(Asked by: username_0 on 2014-01-03)

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.

**Tags:** cc.complexity-theory, polynomials, polynomial-time, quadratic
> **Comments:**
> **username_1**: I may be missing something: What is the difference with [your previous question](http://cstheory.stackexchange.com/questions/20139/what-are-some-efficient-algorithms-for-finding-the-solutions-to-a-quadratic-mult) or [Nick's question](http://cstheory.stackexchange.com/questions/19832/what-are-some-efficient-algorithms-for-determining-if-a-quadratic-multivariate-p)?  
> **username_0**: @Bruno This is for a system of equations. Those other two are for just one polynomial.  
> **username_0**: I thought a system of equations would be a different question. Why the downvotes? Should I change the meaning of my existing question instead of asking a new one?  
> **username_1**: Ok for the difference. I just had the impress of a lot of very similar questions in a very short time. I would suggest that you give the variants of your question in the first of you question. I would be clearer I think.  
> **username_2**: Joe, I agree, this doesn't seem to be a duplicate of those prior questions.  However, people might have downvoted because your question didn't show any evidence of prior research.  (We expect you to do substantial research on your own before asking.)  Also, I recommend that you edit the question with the answers to questions asked over on those other threads, e.g. a rough estimate of the number of variables and of the number of polynomials.  If you're looking for a practical solution, this might make a big difference.  

---

## 1 answers

### Answer by username_2 on 2014-01-04. Score: 3 | Accepted answer

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/351>
* If $m = \omega(n)$ and $m = o(n^2)$, I don't know what the complexity is.

There are also [Grobner basis](https://en.wikipedia.org/wiki/Gr%C3%B6bner_basis) algorithms, the [XL and XSL algorithms](https://en.wikipedia.org/wiki/XSL_attack), 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.


---

