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.

  • 3
    $\begingroup$ I may be missing something: What is the difference with your previous question or Nick's question? $\endgroup$ – Bruno Jan 3 '14 at 10:30
  • $\begingroup$ @Bruno This is for a system of equations. Those other two are for just one polynomial. $\endgroup$ – Joe Jan 3 '14 at 18:58
  • 1
    $\begingroup$ 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? $\endgroup$ – Joe Jan 3 '14 at 19:00
  • $\begingroup$ 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. $\endgroup$ – Bruno Jan 3 '14 at 19:30
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Jan 4 '14 at 3:53

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.