edited by
1,025 views
5 votes
5 votes

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_1^3 -x_1x_2+2$ has the binary root $(x_1=1, x_2=0)$. Then determining whether a multivariate polynomial, given as the sum of monimials, has a binary root:

  1. is trivial: every polynomial has a binary root
  2. can be done in polynomial time
  3. is NP-hard, but not in NP
  4. is in NP, but not in P and not NP-hard
  5. is both in NP and NP-hard
edited by

1 Answer

4 votes
4 votes

This problem is similar to Boolean Satisfiability Problem (SAT) problem which is First NP-Complete problem.

A problem is NP-Complete it means it is in NP as well as NP-Hard, i.e. intersection of both NP and NP-Hard is NP-Complete.

Hence, option (E) is right.

Answer:

Related questions