Tessellate S.T.E.M.S - Computer Science - College - Set 1 - Problem 2

Computer Science Level 4

A multivariate polynomial in $n$ variables with integer coefficients has a binary root if it is possible to assign each variable either $0$ or $1$ , so that the polynomial evaluates to $0$ . For example, the multivariate polynomial $-2x^3 - xy + 2$ has the binary root $x = 1, y = 0$ . Then determining whether a multivariate polynomial, given as the sum of monomials, has a binary root:

This problem is a part of Tessellate S.T.E.M.S.

is in NP, but not in P and not NP-hard is NP-hard, but not in NP is both in NP and NP-hard is trivial: every polynomial has a binary root can be done in polynomial time

1 solution

Abhishek Sinha
Dec 24, 2017

Easy reduction from 3-SAT to this problem. Consider a 3-SAT instance with $n$ variables and $m$ clauses. For each complemented variable $\overline{x_j}$ in a clause, introduce a term $t_j=x_j$ and for each uncomplemeted variable $x_j$ introduce a term $t_j=1-x_j$ . Now, for each clause $C_i$ introduce a term $p_i=1- \prod_{j=1}^3 t_j$ . Clearly, $p_i=1$ iff the corresponding clause is satisfed, otherwise $p_i=0$ . With $m$ clauses, the 3-SAT instance reduces to $\sum_i p_i=m,$ which becomes an instance of the given decision problem once we expand the products (consisting of only three terms) into polynomials.

Clean and elegant solution!

Agnishom Chattopadhyay - 3 years, 5 months ago

Tessellate S.T.E.M.S - Computer Science - College - Set 1 - Problem 2

1 solution

0 pending reports