3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Joshua Grochow Mar 3 '17 at 0:47
  • 3
    $\begingroup$ 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? $\endgroup$ – D.W. Mar 3 '17 at 1:12
  • $\begingroup$ D.W: I was thinking only about a single degree-$2$ polynomial. Thanks for the answers :) $\endgroup$ – Vivek Bagaria Mar 3 '17 at 3:08
  • 3
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Mar 3 '17 at 8:24
7
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.