patternMinor
Is deciding if there's a solution to a single multivariate quadratic equation NP-hard?
Viewed 0 times
solutionhardsingledecidingthereequationmultivariatequadratic
Problem
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.
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.
Solution
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}$.
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}$.
Context
StackExchange Computer Science Q#72656, answer score: 3
Revisions (0)
No revisions yet.