Parisi关于组合优化问题的分析。
reference: * Analytic and Algorithmic Solution of Random Satisfiability Problems
关于组合优化问题关心两类求解算法、理论分析，第二类理论分析具体为一类组合优化问题在不同实例的情况下，有哪些共性特征。
考虑热力学极限α = M/N，其中N是变量数，M是子句数目，其中α是一个恒定值。将其转化为统计物理问题，N个布尔变量用二值s表示，每个子句a包含k个变量（K-SAT问题）即k个自旋相互作用，相互作用强度J ∈ {−1, 1}通过子句中的¬决定，将所有子句进行加和：
$$\begin{align} H=\sum_a \prod_k \frac{1+J_a s_k}{2^k} \end{align}$$
最终H的值表示违反的关系的个数，当全部满足的时候H = 0。定义零温下的自由能关系：
exp (−NyΦ(y)) = ∫𝕕wexp (N[Σ(e) − ye])
其中e表示自由能，Σ为对应自由能量的熵。为了计算Φ，使用空腔的方法。
$\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}$
上图为表示空腔的因子图。
相图可以用如上的结果表示，红线代表平均每个变量不满足的几率；绿线代表遍历性破缺线条；蓝线表示解的熵线。