4
$\begingroup$

I know that given a system of multivariate quadratic equations (i.e, of the form $x^T Ax+b^T x=c$), deciding if there's a solution is NP-hard.

Is deciding if there's a solution to a single multivariate quadratic equation NP-hard too?

I am intersted in the NP-hardness of deciding if there's a solution to a single quadratic equation over any field; not only over $\mathbb R$.

I am currently trying to reduce from the problem of deciding whether there's a solution to the equation $x^T Ax=\lambda$ subject to $x\in[0,1]^n$ (which is NP-complete) to our problem using Lagrange multipliers.

$\endgroup$
  • $\begingroup$ $[0,1]^n$ can be interpreted as a vector space over the field $\mathrm{F}_2$. So solving this over any field is NP-hard, given your NP-complete problem. Perhaps you mean to determine for which fields this problem is NP-hard? Or do you mean that you wish to find some field where the equation holds? $\endgroup$ – Discrete lizard Apr 9 '17 at 9:33
  • $\begingroup$ @Discretelizard When I said $[0,1]^n$ it was specifically over the field $\mathbb R$. Besides, I wanted to determine for which fields this problem is NP-hard. $\endgroup$ – Dudi Frid Apr 11 '17 at 14:02
3
$\begingroup$

For $\mathbb{R}$ (the real numbers), you can decide whether a single multivariate quadratic equation has any real roots or not, in polynomial time. See https://cstheory.stackexchange.com/a/19858/5038. There are some other answers to that question that partly address the case of other fields.

For $\mathbb{F}_2$ (the integers modulo two), you can decide whether there is a root in polynomial time. See https://cstheory.stackexchange.com/q/37687/5038.

I don't know what the situation is for $\mathbb{Q}$ or $\mathbb{F}_{p^n}$.

$\endgroup$
1
$\begingroup$

It doesn't look like. The intuition that for example when $A$ is positive definite you can find a minimum and check if it is less than $c$.

Here is the approach to solve these equations.

Firstly, diagonalize $A = Q \Lambda Q^T$, where $Q$ is unitary. Then you have

$$ x^T Q \Lambda Q^T x + b^Tx = c $$

Substitute $y = Q^T x$ (then $x = Qy$).

You have $$ y^T\Lambda y + b^TQy = c $$

Here, denote $d^T = b^TQ$, and you have very simple equation $$ y^T \Lambda y + d^Ty = c $$ where $\Lambda$ is a diagonal matrix of eigenvalues.

You can do even more and get rid of a linear part by taking the square like $ax^2+bx = a(x^2 + \frac{b}{a}x) = a(x+\frac{b}{2a})^2-\frac{b^2}{4a}$ for every coordinate. Here several cases follows:

  1. if all eigenvalues $>0$ you have paraboloid so simply finding minimum and checking if it is less than $c$ will answer your question.
  2. if all eigenvalues $<0$ you have paraboloid and checking it maximum and checking if it is greater than $c$ will answer the question.
  3. if there is an eigenvalue 0 and corresponding linear coefficient is not 0 than solution exists (for some $i$ you have $d_iy_i = c$, then $y_i = \frac{c}{d_i}$).
  4. You have a saddle i.e. there is a eigenvalue > 0 and eigenvalue < 0. Then tending those coordinates to plus/minus infinity you see that your functions image is the whole $\mathbb{R}$ so there must be a solution.
  5. if all eigenvalues and linear coefficients are 0 then there is a solution iff $c=0$.

The $\mathcal{NP}$-hard part comes into a play when you have restrictions on the domain for example a unit box.

$\endgroup$
  • $\begingroup$ What to do when $A$ is not diagonalisable? Does this approach require some continuity over your field? $\endgroup$ – Discrete lizard Apr 9 '17 at 9:39
  • $\begingroup$ $A$ is symmetric matrix and thus all eigenvalues are real. Thus $A=Q^T \Lambda Q$ must exist. $\endgroup$ – Eugene Apr 9 '17 at 9:42
  • $\begingroup$ I don't see a requirement that $A$ is symmetric or that the values of $A$ are real in the question. Why can we assume the symmetry of $A$? $\endgroup$ – Discrete lizard Apr 9 '17 at 9:44
  • $\begingroup$ Because when you write quadratic form you have that $A$ is symmetric. See en.m.wikipedia.org/wiki/Quadratic_form $\endgroup$ – Eugene Apr 9 '17 at 9:45
  • $\begingroup$ Moreover, the implication is that for every quadratic form there exists a symmetric matrix representing it in the form OP had given $\endgroup$ – Eugene Apr 9 '17 at 9:47

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.