Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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$.)
