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

Question

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.

Answer 1

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

Answer 2

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.