HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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.

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

Context

StackExchange Computer Science Q#72656, answer score: 3

Revisions (0)

No revisions yet.