Analytic and Algorithmic Solution of Random Satisfiability Problems

Parisi关于组合优化问题的分析。

reference:

• Analytic and Algorithmic Solution of Random Satisfiability Problems

关于组合优化问题关心两类求解算法、理论分析，第二类理论分析具体为一类组合优化问题在不同实例的情况下，有哪些共性特征。

考虑热力学极限$\alpha=M/N$，其中$N$是变量数，$M$是子句数目，其中$\alpha$是一个恒定值。将其转化为统计物理问题，$N$个布尔变量用二值$s$表示，每个子句$a$包含$k$个变量（K-SAT问题）即$k$个自旋相互作用，相互作用强度$J\in\{-1,1\}$通过子句中的$\neg$决定，将所有子句进行加和：

$$\begin{align} H=\sum_a \prod_k \frac{1+J_a s_k}{2^k} \end{align}$$

最终$H$的值表示违反的关系的个数，当全部满足的时候$H=0$。定义零温下的自由能关系：

$$\exp(-Ny\Phi(y))=\int\mathbb{d}w \exp(N[\Sigma(e)-ye])$$

其中$e$表示自由能，$\Sigma$为对应自由能量的熵。为了计算$\Phi$，使用空腔的方法。

$\begin{aligned}
\min _{s_2, \ldots, s_K}\left(H-\frac{1}{2} \sum_{j=2}^K h_j s_j\right) =-\frac{1}{2}\left[a_J\left(h_2, \ldots, h_K\right)+s_1 u_J\left(h_2, \ldots, h_K\right)\right]
\end{aligned}$

上图为表示空腔的因子图。

相图可以用如上的结果表示，红线代表平均每个变量不满足的几率；绿线代表遍历性破缺线条；蓝线表示解的熵线。