Minimizing a multivariate polynomial over the hyper-cube is NP-Hard - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-21T23:46:48Z https://cs.stackexchange.com/feeds/question/11246 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/11246 4 Minimizing a multivariate polynomial over the hyper-cube is NP-Hard fran.aubry https://cs.stackexchange.com/users/7697 2013-04-11T15:42:38Z 2013-04-12T03:01:45Z <p>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$?</p> <p>My idea is to reduce it to MAX-SAT as follows. Suppose I am given the formula:</p> <p>$(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})$</p> <p>Then I consider:</p> <p>$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)$</p> <p>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?</p> https://cs.stackexchange.com/questions/11246/-/11249#11249 1 Answer by Yuval Filmus for Minimizing a multivariate polynomial over the hyper-cube is NP-Hard Yuval Filmus https://cs.stackexchange.com/users/683 2013-04-12T03:01:45Z 2013-04-12T03:01:45Z <p>Hint: Modify your polynomial slightly so that (a) it is always negative, (b) its only zeroes are solutions to SAT.</p>