patternMinor
Transforming SAT to Quadratic Programming in polynomial time
Viewed 0 times
satpolynomialtransformingprogrammingtimequadratic
Problem
I would like to show that Quadratic Programming is NP-hard.
I am currently reading a couple of papers which state that QP is NP-Hard and prove it by transforming SAT to QP, however I am finding the diction quite tough since I am just a beginner in the field. Would anyone happen to know the answer to this question who can maybe explain it to me in simpler terms?
I am currently reading a couple of papers which state that QP is NP-Hard and prove it by transforming SAT to QP, however I am finding the diction quite tough since I am just a beginner in the field. Would anyone happen to know the answer to this question who can maybe explain it to me in simpler terms?
Solution
The reduction of SAT to quadratic programming is pretty simple. The idea is that we can use the quadratic objective to "force" the variables to be Boolean, and so we can implement an integer linear program whose feasibility is equivalent to the SAT instance.
Given a SAT instance on a set of variables $x_1,\ldots,x_n$, we define the following quadratic program:
$$
\begin{align*}
& \min \sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 \\
\text{s.t.} & \\
& 0 \leq x_i \leq 1 & 1 \leq i \leq n \\
& x_{i_1} + \cdots + x_{i_j} + (1 - x_{k_1}) + \cdots + (1 - x_{k_\ell}) \geq 1 & \forall \text{ cl. } x_{i_1} \lor \cdots \lor x_{i_j} \lor \bar{x}_{k_1} \lor \cdots \lor \bar{x}_{k_l}
\end{align*}
$$
The linear constraints have a $0,1$ solution if and only if the SAT instance is satisfiable. Since $0 \leq x_i \leq 1$, a solution is $0,1$ if and only if $\sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 = 0$, and for any other solution $\sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 > 0$. Therefore the SAT instance is satisfiable if and only if the minimum is $0$ (or at most $0$).
Given a SAT instance on a set of variables $x_1,\ldots,x_n$, we define the following quadratic program:
$$
\begin{align*}
& \min \sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 \\
\text{s.t.} & \\
& 0 \leq x_i \leq 1 & 1 \leq i \leq n \\
& x_{i_1} + \cdots + x_{i_j} + (1 - x_{k_1}) + \cdots + (1 - x_{k_\ell}) \geq 1 & \forall \text{ cl. } x_{i_1} \lor \cdots \lor x_{i_j} \lor \bar{x}_{k_1} \lor \cdots \lor \bar{x}_{k_l}
\end{align*}
$$
The linear constraints have a $0,1$ solution if and only if the SAT instance is satisfiable. Since $0 \leq x_i \leq 1$, a solution is $0,1$ if and only if $\sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 = 0$, and for any other solution $\sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 > 0$. Therefore the SAT instance is satisfiable if and only if the minimum is $0$ (or at most $0$).
Context
StackExchange Computer Science Q#17946, answer score: 6
Revisions (0)
No revisions yet.