<p>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:</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-03-03T08:26:13.927Z
Indeed, NP-hardness is for systems of degree-3 polynomials, not for individual degree-3 polynomials.
Joshua Grochow
CC BY-SA 3.0
2017-03-03T05:49:45.570Z
2017-03-03T05:49:45.570Z
Andrew Morgan
<p>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</p>

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

<p>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).</p>

<p>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)$.</p>

<p>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</p>

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

<p>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$.)</p>

CC BY-SA 3.0
2017-03-03T05:40:08.823Z
2017-03-03T05:40:08.823Z
D.W.
<p>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. </p>

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

CC BY-SA 3.0
2017-03-03T00:47:24.063Z
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
CC BY-SA 3.0
2017-03-03T01:12:21.303Z
Looks like duplicate of http://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 http://mathoverflow.net/a/153467/37212.    (See also http://cs.stackexchange.com/q/9678/755, http://crypto.stackexchange.com/q/3723/351, http://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.
CC BY-SA 3.0
2017-03-03T03:08:19.273Z
D.W: I was thinking only about a single degree-$2$ polynomial. Thanks for the answers :)
Vivek Bagaria
CC BY-SA 3.0
2017-03-03T08:24:53.010Z
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
<reference-request><np-hardness><sat><polynomials><finite-fields>
Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$
Vivek Bagaria
# Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$

(Asked by: username_0 on 2017-03-02)

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?

**Tags:** reference-request, np-hardness, sat, polynomials, finite-fields

> **Comments:**
> **username_1**: 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?  
> **username_2**: Looks like duplicate of http://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 http://mathoverflow.net/a/153467/37212.    (See also http://cs.stackexchange.com/q/9678/755, http://crypto.stackexchange.com/q/3723/351, http://cstheory.stackexchange.com/q/20420/5038.)  Please edit the question to clarify the point raised by username_1.  Then maybe you might want to answer your own question?  
> **username_0**: D.W: I was thinking only about a single degree-$2$ polynomial. Thanks for the answers :)  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_3 on 2017-03-03. Score: 7

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.

> **Comments:**
> **username_1**: Indeed, NP-hardness is for systems of degree-3 polynomials, not for individual degree-3 polynomials.  

---

### Answer by username_2 on 2017-03-03. Score: 3

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


---

