2 edited tags

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?

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?

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?

Post Migrated Here from cstheory.stackexchange.com
1

# Minimizing a multivariate polynomial over the hyper-cube is NP-Hard

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?