Tweeted twitter.com/#!/StackCompSci/status/340875013664165889
2 edited tags
source | link

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?

Thank you in advance.

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?

Thank you in advance.

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
source | link

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?

Thank you in advance.