引言
这篇进入物理中的计算理论正题，探讨两个经典自旋系统的NP困难性质。我们利用上次证明的两个 cubic graph 上的NP完全问题，来约化到对应的物理自旋系统的基态能量判定问题，从而完成该证明。这篇文章的主要思路参考 [1] 的第四部分。
3D spin glass
问题
给定 \(H=-\sum_{<ij>}J_{ij}S_iS_j\)，其中经典自旋自由度可以在 \(\pm 1\) 中取值，\(J_{ij}\) 可以在 \(0,\pm1\) 取值，这种 Ising type 的相互作用定义在图上的所有边上。我们要证明以下问题是NP完全的：
给定这样一个具体的H和对应的格点图G以及整数\(E_0\)，是否存在自旋的构型使得该模型的基态能量不大于\(E_0\)?
注意到该问题中，相互作用的强度和自旋构型的取值总是整数，那么对应的最后的基态能量一定是一个整数。该问题一定处在 NP，因为给定一个构型，可以\(O(n^2)\)步骤内验证是否成立。
如果以上问题被证明是NP完全的，考虑我们可以求得该系统的配分函数 \(Z(\beta)\)。我们取温度倒数 \(\beta > (N+1)\ln 2\)（N 为图的顶点数），那么此时系统的平均能量为 \(\langle E\rangle = -\frac{\partial Z}{\partial\beta}\)。若该值大于\(E_0+1\)，则原基态判别问题的答案为否；若该值小于\(E_0+\frac{1}{2}\)，则原基态判别问题的答案为是。因此若我们可以在多项式时间求的系统配分函数，原基态能量问题就得到了解答。也就是说证明了基态能量判别问题的NP完全，也同时证明了同样系统配分函数计算的NP困难。
上述配分函数夹逼基态能量的分析，可以通过非常松的限制得到。考虑N个顶点的图，则一共具有\(2^N\)个构型，使得基态能量为\(E_0\)，且对于平均能量分析降低最不利的构型分布，就是只有一个基态，其他\(2^N-1\)态都处在能量\(E_0+1\)，这当然是不可能的，不过这么 loose 的限制，已经足以使我们将平均能量控制在\(E_0+1\)之下了。
两层方格子
我们证明的路线图是从上篇提到的 cubic graph 上的 MAX CUT 的问题，归约到一个所谓的两层方格子问题，在从两层方格子问题归约到上述的基态能量判别问题。这一部分我们完成第一步的归约，为此先证明一个引理：
对于图的每个边，都用若干条边和新增顶点来代替，且其中各边的权重均为1，只有一条边权重为-1，那么现在的图上存在权重至多为 -k 的 CUT，等价于原图存在至少为 k 的 simple CUT。
必要性很容易证明，对于原图上一个 k 的 CUT，在新图以-1权边为界，分别指定各新顶点的选择情况即可。而对于存在性，当cut总权重为－k时，考虑有p次跨越-1边，也即p个-1权边，都指定边的某一端点被选定。将这些端点按照同样的选定方式延伸回原图顶点，若自洽，则 k=p，证毕。若不自洽，这选择该端点与更多邻点的选定性质相一致，不一致的边数记为q，则 k=p-q。将这种选取对应回原图，p个边中，有q个两端点同时选中或为选中，对应的 simple cut 为 p-q=k。证毕
现在我们考虑一个两层立方格子，每个边都指定一个取值为\(0,\pm1\)的权重，我们证明这样的加权图上，以下问题是NP完全的：
给定满足上述条件的图和整数k，该图上是否存在 cut 权重不大于 k。
证明方法是将 cubic graph 上的 MAX CUT 约化到该问题。其构造如下。
利用顶点数为n，边数为m的 cubic graph 构造两层的方格子，记为图G‘。G’ 的顶点共有\(2nm\)个，顶点记为\(V'=\{[v_i,e_j,f]\vert 1\leq i\leq n,1\leq j\leq m,1\leq f\leq 2\}\)。现在我们构造边。对于原图的每个边\(e_j=(v_i,v_{i+p})\)，我们在第一层的顶点构建边\(([v_i,e_j,1],[v_{i+1},e_j,1]),([v_{i+1},e_j,1],[v_{i+2},e_j,1]),([v_{i+p-1},e_j,1],[v_{i+p},e_j,1])\)。每一组这样的边在第一层方格子的某列形成一个路径，在这一路径上的这些边上，我们随意指定一个边的权重为-1，其他边权重为1。在第二层方格子，对于原图的每个顶点\(v_i\)，其对应的三条边记为\(e_j,e_{j+p},e_{j+p+q}\)，那么在第二层对应\(v_i\)的行，连接一条从\([v_i,e_j,2]\)到\([v_i,e_{j+p+q},2]\)的路径。该路径的每条边的权重均为1。最后我们在构建连接两侧顶点的边，如果边\(e_j\)的一个端点是\(v_i\)，则我们连接两侧的对应在方格子中的顶点，也即\(([v_i,e_j,1],[v_i,e_j,2])\)。其他所有未涉及的方格子上的边权重为0，全部构造完毕。这一构造仅需多项式时间。
如果我们把二层方格子图的顶点\([v_i,e_{j+p},2]\) （\(e_{j+p}\)是指从\(v_i\)顶点出发的，排序在中间的边）视为对应原 cubic 图的顶点，那么这一新构造的图恰好是按照引理方式从原 cubic 图上构造出的。那么根据引理，这一两层方格子的 min weight cut 判别问题等价于原 cubic 图上的 max cut 问题，因此两层方格子问题是NP完全的。
自旋系统
现在回到问题部分提出的自旋系统基态能量判别问题，只需把两层方格子问题，约化到这一自旋问题，即最终完成了这一自旋系统是NP完全的证明。这一证明，结合上篇内容，完整的约化逻辑链为：3SAT，nae 3SAT，nae 2-3SAT，cubic graph 上的 MAX CUT，两层方格子问题，3维自旋问题。
现在考虑两层方格子上的自旋模型，\(J_{ij}=\pm1,0\)，\(S_i=\pm 1\)，我们证明该两层方格子图存在一个权重为 W 的 cut，等价于其上的自旋模型能量为 \(H=2W-\sum_{(i,j)\in E}J_{ij}\)。充分性：将对应 cut 选定的顶点上的自旋取为 1，其他顶点的自旋取为-1，显然能量为上述值。必要性：若存在某构型能量可取上值，将构型中自旋为1的格点取为cut的选中顶点，显然该 cut 的权重为 W。这样如果我们能够多项式时间解决两层方格子上的 spin glass 模型，我们就解决了两层方格子问题，也就解决了 cubic graph 上的 MAX CUT 问题。由此可知一般的三维 spin glass 系统是NP完全的。
2D spin model with magnetic field
问题
给定\(H=\sum_{(i,j)\in E}S_iS_j+\sum_{i\in V}S_i\)，及二维格点，自旋取值为\(\pm 1\)，那么对应的基态能量判别问题可以证明是NP完全的。注意这里的 coupling 即使均为 \(J_{ij}=-1\)，也已经NP完全。这一哈密顿量对应的物理系统是加了均匀外磁场的反铁磁系统。这次的证明路线是从 planar cubic graph 上的 max independent set 问题归约到该二维自旋系统，从而证明其NP完全性。
证明
对于 planar cubic graph 上的每个顶点考虑变量 \(X_i=1,0\)，容易得到 \(L=\sum_{i\in V}X_i-\sum_{(i,j)\in E}X_iX_j\geq k\)，等价于该图上的 max indepedent set 不小于 k。只需令该 set 内的顶点变量设为1，其他设为0即可。做替换\(S_i=2X_i-1\)，我们有 \(L=-\frac{1}{4}\sum_{i\in V}S_i-\frac{1}{4}\sum_{(i,j)\in E}S_iS_j+\frac{1}{8}\vert V\vert\)。所以对于一个二维模型，若存在构型使得\(H\leq \frac{1}{2}\vert V \vert-4k\)，则原 cubic graph 具有不小于 k 的 independent set。由此可得，有外磁场的二维经典自旋模型是NP完全的。
需要注意完成该证明，只需有前提 planar degree m 的图上 max independent set 是NP完全问题，m不一定必须为3。但若前提只有 at most degree m 的话，则只能证明不均匀磁场的情形，模型是NP完全的。
Reference
- F. Barahona, On the computational complexity of Ising spin glass models, J. Phys. A: Math. Gen 15, 3241 (1982).
EOF