4
$\begingroup$

In an exercise I have to show that minimizing a multivariate polynomial with $n$ variables over the hyper-cube $H = \{ (x_1, \ldots, x_n) : 0 \leq x_i \leq 1 \}$ is NP-Hard. Formally, given $p(x_1, \ldots, x_n)$ and $\alpha$, does $\min_{0 \leq x_i \leq 1} p(x_1, \ldots, x_n) \leq \alpha$?

My idea is to reduce it to MAX-SAT as follows. Suppose I am given the formula:

$(x_1 \vee \overline{x_2} \vee x_3) \wedge (\overline{x_1} \vee \overline{x_3}) \wedge (\overline{x_1} \vee x_2 \vee \overline{x_3})$

Then I consider:

$p(y_1, y_2, y_3) = y_1 (1 - y_2) y_3 + (1 - y_1) (1 - y_3) + (1 - y_1) y_2 (1 - y_3)$

If $p$ reaches a minimum at a corner of $H$ then the assignment: $$x_i = \textit{true} \ \text{if} \ y_i = 0 \ \text{and} \ x_i = \textit{false} \ \text{if} \ y_i = 1$$ is a solution for MAX-SAT value for the corresponding formula and since MAX-SAT is NP-Hard we are done. However, how do I proceed if $p$ reaches its minimum at an interior point? Or is it the case that it will always be a corner?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ Hint: construct a non-negative polynomials whose only zeroes are solutions to SAT. $\endgroup$
    – Yuval Filmus
    Apr 11, 2013 at 16:08
  • $\begingroup$ I did express the problem correctly. I edited it now. I actually do not want the minimum but to find if it is smaller than $\alpha$. $\endgroup$
    – fran.aubry
    Apr 11, 2013 at 17:59

1 Answer 1

Reset to default
1
$\begingroup$

Hint: Modify your polynomial slightly so that (a) it is always negative, (b) its only zeroes are solutions to SAT.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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