15
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ See also mathoverflow.net/questions/119213/…. $\endgroup$
    – Dietrich Burde
    Commented Jan 3, 2014 at 11:59
  • 3
    $\begingroup$ Could you clarify: do you want to find all solutions or just one solution? The way the question is phrased currently appears incomplete -- can you efficiently find $x_1,\dots,x_n$ so that what?? Also, what are the coefficients of the polynomials in $P$? $\endgroup$
    – Vidit Nanda
    Commented Jan 3, 2014 at 12:29

3 Answers 3

Reset to default
20
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ It might be worth mentioning that while testing solvability of polynomial systems (aka the existential theory of the reals) is indeed NP-hard, it’s actual complexity may well be even higher. The only known upper bound is PSPACE. $\endgroup$
    – Emil Jeřábek
    Commented Jan 3, 2014 at 17:38
14
$\begingroup$

The quadratic case is as complex as the general case (up to a polynomial-time reduction). Given a set of polynomials $\{p_1,\dots,p_m\}$, you can express each $p_i$ by a straight-line program with instructions of the form $x_i:=c$ ($c\in\mathbb R$ a constant), $x_i:=x_j+x_k$, and $x_i:=x_j\cdot x_k$, which you can in turn translate back to quadratic polynomials (e.g., the last mentioned instruction becomes $x_i-x_jx_k$). The number of variables in the new system will increase (it is linear in the size of the original system), which suggests that you might get an efficient solution if you additionally restrict the number of variables by a constant.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ it is well-known that one can find representatives of connected components of real algebraic sets in $\mathbb{R}^n$ encoded by degree $d$ polynomials in $O(d)^{O(n)}$ ring operations. And $n$ in the exponent is not avoidable, generally speaking, unless P=NP. $\endgroup$
    – Dima Pasechnik
    Commented Jan 3, 2014 at 13:28
9
$\begingroup$

There have been written many books and articles on this subject (see for example the book "Sturmfels, Bernd, Solving systems of polynomial equations. American Mathematical Society, Providence, RI, 2002").
It is not the fact that the polynomials are quadratic which helps, but rather other restrictions which will sometimes result in a more effective solution. If the Groebner basis of the corresponding ideal in $K[x_1,\ldots ,x_n]$ can be computed, and has triangular form, then we can usually solve the system. However, Groebner bases have large exponential complexity and cannot solve in practice systems with, say, more than $15$ variables.
For some overdetermined systems there are other techniques than Groebner bases. One of these is called "relinearization". The exact complexity of this algorithm is not known, but for sufficiently overdetermined systems it is expected to run in polynomial time (see papers by Nicolas Courtois; Alexander Klimov, Jacques Patarin, and Adi Shamir).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .