# Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$

Since every $3$-SAT instance with $n$ variables can be expressed as a degree-$3$ polynomial over $\mathbb{F}_2$ with $n$ unknowns, the NP-hardness of $3$-SAT directly translates to NP-hardness of solving(finding roots) $3$-degree polynomials.

So my question is solving a single degree-$2$ polynomial over $\mathbb{F}_2$ with $n$ unknowns, NP-hard?

• Is your question about finding roots of a single degree-2 polynomial given as input, or a system of several degree-2 polynomials given as input? – Joshua Grochow Mar 3 '17 at 0:47
• Looks like duplicate of cstheory.stackexchange.com/q/33698/5038, assuming you mean a system of polynomials; otherwise it is trivially solvable in P. Also, the answer follows from mathoverflow.net/a/153467/37212. (See also cs.stackexchange.com/q/9678/755, crypto.stackexchange.com/q/3723/351, cstheory.stackexchange.com/q/20420/5038.) Please edit the question to clarify the point raised by Joshua Grochow. Then maybe you might want to answer your own question? – D.W. Mar 3 '17 at 1:12
• D.W: I was thinking only about a single degree-$2$ polynomial. Thanks for the answers :) – Vivek Bagaria Mar 3 '17 at 3:08
• FYI, the NP-hardness for degree-3 polynomials is for a system of degree-3 polynomials: you get one degree-3 polynomial for each clause in a 3SAT instance, and if you try to combine these all into a single polynomial then the degree increases significantly. – Joshua Grochow Mar 3 '17 at 8:24

It's easy, and in fact I suspect your proof that the "degree-3 version is NP-hard" is flawed somewhere, since the degree-3 version is also easy. Here's the argument for degree-2:

Suppose our constraint is $p(x) = 1$, and assume, since we're only interested in $p$ as a function, that it is reduced mod $x_i^2 = x_i$ (ie that it's multilinear). We can plug in zero, and if it fails to satisfy the constraint, we can conclude that $p$ has no constant term. Next, we try all points of Hamming weight 1. If they all fail to satisfy the constraint, then, since $p$ has no constant term, this means $p$ has no terms of degree 1. [To see this, think of what a Hamming-weight-1 input does to each monomial.] Next we try all points of Hamming weight 2, and, again, if these fail, then, since $p$ has no terms of degree at most 1, this means $p$ has no terms of degree 2. Since $p$ has degree at most 2, the only way these can all fail is if $p$ is the zero polynomial, and of course no solution exists in that case.

This keeps going to higher degrees: (the multilinearization of) $p$ has no terms of degree at most $r$ iff it's zero on all points of Hamming weight at most $r$. So for any constant degree, you get an efficient algorithm.

• Indeed, NP-hardness is for systems of degree-3 polynomials, not for individual degree-3 polynomials. – Joshua Grochow Mar 3 '17 at 8:26

It's not NP-hard, unless P=NP. There is a polynomial-time algorithm to determine whether a single quadratic polynomial $f(x_1,\dots,x_n)$ has any zeros over $\mathbb{F}_2$, and if it does, to output one such zero. Write

$$f(x_1,\dots,x_n) = g(x_1,\dots,x_{n-1}) x_n + h(x_1,\dots,x_{n-1})$$

where $g$ is a degree-1 polynomial and $h$ is a degree-2 polynomial. Test whether $h(x_1,\dots,x_{n-1})$ has any zeroes over $\mathbb{F}_2$ (recursively).

If it does, then using that value of $x_1,\dots,x_{n-1}$ and setting $x_n=0$ gives a zero of $f(x_1,\dots,x_n)$.

Alternatively, if $h(x_1,\dots,x_{n-1})$ has no zeroes, then it follows that $h(x_1,\dots,x_{n-1})=1$ for all $x_1,\dots,x_{n-1}$, so we have

$$f(x_1,\dots,x_n) = g(x_1,\dots,x_{n-1}) x_n + 1.$$

You can check whether this has any zeros by setting $x_n=1$ and checking whether $g(x_1,\dots,x_{n-1}) + 1$ has any zeroes (which can be done using linear algebra, as $g$ has degree 1). (Obviously $x_n=0$ cannot lead to a zero of $f$ if $h$ is identically $1$, so there is no need to consider the case where $x_n=0$.)