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

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.

• $[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? – Discrete lizard Apr 9 '17 at 9:33
• @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. – Dudi Frid Apr 11 '17 at 14:02

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

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.

• What to do when $A$ is not diagonalisable? Does this approach require some continuity over your field? – Discrete lizard Apr 9 '17 at 9:39
• $A$ is symmetric matrix and thus all eigenvalues are real. Thus $A=Q^T \Lambda Q$ must exist. – Eugene Apr 9 '17 at 9:42
• 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$? – Discrete lizard Apr 9 '17 at 9:44
• Because when you write quadratic form you have that $A$ is symmetric. See en.m.wikipedia.org/wiki/Quadratic_form – Eugene Apr 9 '17 at 9:45
• Moreover, the implication is that for every quadratic form there exists a symmetric matrix representing it in the form OP had given – Eugene Apr 9 '17 at 9:47