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.
5
-
3$\begingroup$ I may be missing something: What is the difference with your previous question or Nick's question? $\endgroup$– BrunoJan 3, 2014 at 10:30
-
$\begingroup$ @Bruno This is for a system of equations. Those other two are for just one polynomial. $\endgroup$– JoeJan 3, 2014 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$– JoeJan 3, 2014 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$– BrunoJan 3, 2014 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, 2014 at 3:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
