# Transforming SAT to Quadratic Programming in polynomial time

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?

• Where should we start? Do you know anything about NP-completeness? Have you seen any examples of NP-completeness proof? – Yuval Filmus Nov 12 '13 at 9:22
• Yes I have a good background on NP-Completeness and how a problem is proven to be NP-complete. My question is more specifically about this particular reduction. I have a feeling that I have not understood QP 100% and I am missing some small thing somewhere. – lvella Nov 12 '13 at 9:30
• Can you give a reference to what Quadratic Programming is? – Raphael Nov 12 '13 at 16:53
• Raphael, by Quadratic Programming I was referring to optimising a quadratic function which is subject to several linear constraints. – lvella Nov 12 '13 at 22:04

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$).
• They represent a clause. For example, the clause $x_7 \lor x_{18} \lor \bar{x}_9$ will result in the inequality $x_7 + x_{18} + (1-x_9) \geq 1$. – Yuval Filmus Nov 12 '13 at 21:37
• Will it work to convert $3SAT$ to MAXCUT or INDSET preserving number of solutions (standard text reductions look like they will preserve solution count) and utilize resulting quadratic objective? – T.... May 16 '18 at 10:49