$$\begin{align} \text{Min}&&\frac{1}{2}\sum_{(i,j,s,t)\in I}\|x_ix_j-x_sx_t\|\\ s.t.: && Ax=b\\ &&x\geq 0 \end{align}$$

具有相同的最优解（因此具有相同的计算复杂度，因为此变换是多项式归约）

$$\begin{align} \text{Min}&&\frac{1}{2}\sum_{(i,j,s,t)\in I}\|x_ix_j-x_sx_t\|^{2}\\ s.t.: && Ax=b\\ &&x\geq 0. \end{align}$$

后一个问题是多项式规划问题，已知为 NP-hard，因为该程序类包含二次规划，这也是 NP-hard。（请参阅全局优化中的复杂性问题：调查，斯蒂芬·瓦瓦西斯（Stephen Vavasis）。）获得约简（正如另一个答案似乎正确地做的那样）是有用的，但没有必要，因为问题可以转化为多项式规划问题。

考虑以下特殊情况（使用从 0 开始的索引）： 换句话说，和。因此，如果我们修复，那么问题会简化为： 和 时，表达式等于零。

$$A = \begin{bmatrix}0&0&0&0&0&1\\0&1&0&0&1&0 \end{bmatrix}, \ b = \begin{bmatrix} 1\\1 \end{bmatrix},\\ I = \{ (0,4,2,3), (0,0,0,5), (1,1,1,5), (2,2,2,5), (3,3,3,5) \}.$$ $x_5=1$$x_4=1-x_1$$x_1,x_2,x_3$ $$\min_{x_0} |x_0 (1-x_1) - x_2 x_3| + \sum_{i=0}^3 |x_i^2 - x_i|$$ $x_i \in \{0,1\}$$x_1 x_2 x_3=0$

因此，通过为每个子句引入额外的变量，可以将任何 3-SAT 问题简化为检查此类程序的最小值是否为零。