• Introduction
• Random field Ising Model
  • Hamiltonian
  • transformation to graph cut
• Max Cut and Min Cut
  • ferro RFIM is in P
  • antiferro RFIM is NP complete
  • comments on max cut vs. min cut
• Discussions on physics implications
  • comparison to other NP hard systems
  • factors make system NP hard
  • what about disorder average
• Sketch on Max Flow Algorithm
• Reference

Introduction

这篇内容作为物理中的计算理论系列，继续讨论另一个著名的经典无序系统的算法复杂度，作为经典统计问题复杂度分析的一个简单补充。我们还会把结果扩展到经典自旋统计系统复杂度的完全分类。同时也会从算法的角度，比较与该物理系统相关的图论中的 Max Cut 和 Min Cut 的复杂度的不对称性。

Random field Ising Model

Hamiltonian

所谓随机场 Ising 模型，是一个经典自旋系统的无序模型，其对应的系统的哈密顿量为：

\[H=-\sum_{\langle ij\rangle}J_{ij}S_iS_j-\sum_i h_i S_i\]

同之前的模型一样，该哈密顿量定义在某个图G上，自旋自由度 \(S_i=\pm 1\) 定义在图的顶点上，自旋自旋耦和项 \(J_{ij}\) 保持同号，定义在图的边上，外磁场 \(h_i\) 可以取正值或负值，定义在图的每个顶点上。当所有 \(J>0\)时，系统被称为铁磁 RFIM，反之所有 \(J<0\) 时，则为反铁磁 RFIM。当然，一般情形下，物理学家研究的 RFIM，都会假定所有的 \(J_{ij}\) 相同，只有随机分布的外磁场项是无序的来源。下面我们会看到，根据问题要证明的复杂度不同，我们可以总是选取哈密顿量定义 （\(J\) 相同或只是同号）， 来使我们的算法复杂度结论更严格。

transformation to graph cut

这一问题的证明，在于将最小能量问题转化为图论的基本问题，我们先假定所有的 \(J_{ij}>0\)，来叙述对应的构造（该构造可参考 [1]）。对于本来模型定义的格点图（如下图左），我们将每个边指定对应的权重(capacity)，为对应的自旋耦和项的系数 \(J_{ij}\)。考虑对应基态判定问题输入的哈密顿量中，\(h_2,h_3>0\)，\(h_1,h_4<0\)，我们在图上补充两个顶点s和t，其中，s 和所有磁场 \(h_i\) 为负的顶点相连，且对应的边的权重为 \(\vert h_i\vert\)；同时 t 和所有磁场 \(h_i\) 为正的顶点相连，对应边的权重为 \(\vert h_i\vert\)。这样我们就得到了一个所有边带正权重的图。

我们发现系统的能量，和这样构造的图的 cut 有着密切的关系。关于 cut 的概念，请参考之前的cubic-graph-上的-NP-完全问题。设想我们取 s 顶点的自旋向下，而 t 点自旋向上 （实际上这两点没有自旋），同时对所有格点的自旋都进行某种取值，那么自旋向上的点的集合和自旋向下的点的集合之间的 cut，就等于这些边的 capacity 之和，我们记为 \(\mathcal{C}\)。很容易看到系统的能量实际上为：

\[E=-E_0+2\mathcal{C}, ~~E_0 = \sum_{ij}J_{ij}+\sum_{i}\vert h_i\vert\]

上式的证明很简单，可以先考虑所有的自旋都是向上，那么对于自旋耦和项，考虑出发点的能量是 \(-\sum J_{ij}\)，真实的能量可以通过逐渐翻转自旋向下来实现，每次翻转增加的能量，恰好对应 cut 上新加的边上的 capacity 的2倍。对于磁场能量项也同理，先考虑系统自旋分布和外磁场分布同向，则对应出发点能量为 \(\sum -\vert h_i\vert\)，然后逐渐翻转自旋到指定的构型，每次违背一个磁场项，都增加 \(2\vert h_i\vert\) 的能量，这恰好对应了翻转顶点和新增顶点 s 或 t 之间的边新进入了 cut。

可以看到系统能量除了一个常数，完全取决于图的 cut 的值。也就是求物理系统的基态能量的问题，完全归结为求对应图的被 s，t 顶点划分的 min cut 问题。

反之对于一个反铁磁的 RFIM，分析和构造完全同理，只不过这时系统的能量变为 \(E_{A}=-E=E_0-2\mathcal{C}\)，此时基态能量的物理问题归约到了图上被 s，t 顶点划分的 max cut 问题。

Max Cut and Min Cut

ferro RFIM is in P

根据 Max Flow Min Cut 定理，基于 s，t 两顶点划分的 min cut 就等价于从 s 到 t 的 max flow。而 max flow 有成熟的多项式算法，因此铁磁耦合的 RFIM 的基态能量判定是一个 P 问题。关于 Max flow min cut 定理，及 max flow 的多项式组合算法，可以参考本文最后部分。注意到该算法不依赖于图的平面性，因此铁磁 RFIM 基态能量的多项式时间解法，在任意维度的格点都存在。由于 \(J_{ij}\) 不全相等的系统都在 P，那么自然物理学家关注的 \(J_{ij}\) 相同的模型，也在 P。

antiferro RFIM is NP complete

而另一方面，我们之前已经证明了任意图上的 max cut 问题是 NP 完全的。因此解决反铁磁的 RFIM 基态能量问题是 NP 完全的。

我上面一段话是骗你的。上面这个NP完全证明有两个问题，第一是没有说明 max cut 问题，和基于两个指定顶点（也即两点必须处于划分的两边）max cut 问题的等价性。第二是我们上节只说明了 RFIM 可以约化为图上的 max cut 问题，但要证明反铁磁 RFIM 的NP完全，逻辑是反过来的，需要说明任意正权重图的 max cut 问题都可以多项式时间约化到反铁磁 RFIM 的基态能量问题。

这两个问题都可以解决。第一个问题比较简单，我们只需把 max cut 问题约化到基于两指定点的 max cut 问题。也就是说，我们要证明基于两指定点的 max cut 问题的解决方法可以用来解决 max cut 问题。具体做法就是，在待求 max cut 的图上，添加两个顶点，并且这两个顶点都以 0 权重的边连接其他所有顶点，然后求基于两个新添加顶点的 max cut 就等价于原图的 max cut 问题。事实上，基于两点的 max cut 和 max cut 难度等价，反方向的证明的构造是，在两个指定点之间添加一条权重是原图所有边权重和的边，然后再对新图求 max cut，则自然指定两点处在不同的划分上。

第二个问题也不困难，只不过在约化中我们会发现，贡献反铁磁 RFIM 难度的部分，可能和大家最关心的随机磁场项无关。要想把任意正权重图上的 max cut 归约到 RFIM 问题，直接构造基于该图格点的反铁磁 RFIM，对应的 \(J_{ij}\) 等于原图边的 capacity，而所有的磁场项 \(h_i=0\) 即可。根据上节的分析，这样的模型的基态能量和原图的 max cut 存在一一对应。于是我们发现，这一NP完全的证明里，我们根本没有到该系统最重要的部分：随机磁场。因此该模型NP困难的这一难度，和问题的核心部分无关。

另一方面，我们希望进一步严格模型的系数，使其仍然NP完全。考虑反铁磁模型中，所有的 \(J_{ij}=1\)，对应图的 simple max cut 问题，仍然 NP 完全。因此我们得到的最严格的 NP 完全模型是任意图上的无磁场耦合均匀的反铁磁模型。

comments on max cut vs. min cut

这节的讨论都限制在边的权重都为正的图上，这一限制很重要，否则很明显 min cut 和 max cut 问题可以相互转换，只需在边权重上加负号即可，两问题在复杂度上将相等。

当仅考虑正权重图时，max cut 是NP完全的，而 min cut 是P问题。这一结论还有最后一个 gap，也即我们只指出了根据 max flow min cut 定理，基于两指定点划分的 min cut 是P问题。我们还需要证明， min cut 本身也是P。具体做法就是，固定一个点，然后和其他点都按照两指定点划分的 min cut，也即 max flow 问题解一遍，这样就找到了不限于两指定点划分的 min cut 的解。这一做法虽然暴力，但只是原来P算法时间的\(\vert V\vert\)倍，因此复杂度意义上，仍是一个P算法。

因此最终的结论是，正权重图上， max cut 问题和基于两点划分的 max cut 问题都是NP完全的；min cut 问题和基于两点划分的 min cut 问题都是在P的。这一图论问题的最后一块拼图是：planar graph 上的正权重图，max cut 问题也是在P的 [2]。

Discussions on physics implications

comparison to other NP hard systems

考虑 \(h_i=0\) 的无外磁场的铁磁 RFIM，易知其仍然是个 P 问题。这一模型与之前NP完全的3D spin glass 的唯一区别在于，前者的 \(J>0\)，后者的 \(J\) 既可以是正的也可以是负的或是0。算法上看，这和 min cut 问题在 P 要求图的所有边 capacity 都为正有关。物理上看，这也与前者可以进行多项式时间有效的 Monte Carlo 模拟，而后者会面临指数时间的 MC update slowing down 相符合。这进一步说明了，通过复杂度理论对系统的复杂度进行划分，这一做法的生命力和有效性。其带给我们关于对应系统本质难度很好的刻画，使得我们对于数值模拟相应系统时面临的困难，有很好的认识。

考虑无外磁场的反铁磁 RFIM，根据上节的证明，由于其联系着图的 max cut 问题，该模型仍为NP完全系统。对比我们之前讲的 2D spin glass is in P。可知反铁磁 RFIM 的难度实际上是来在于非平面图的部分。其平面图的模型是 2D spin glass 的一个特例，仍然可以在多项式时间解答。因此我们又有了上节NP完全模型的更严格的限制：无外场自旋耦和均匀的任意3D图上的反铁磁系统是NP完全的。这在一定程度上也符合物理直觉，因为物理上我们会遇到很多模型，当 coupling 从正变负（从铁磁到反铁磁），本来简单的问题就突然变难了。

我们将 \(H=\sum_{\langle ij\rangle}-J_{ij}S_iS_j＋\sum_ih_iS_i\) 的自旋系统相关的复杂度结论总结如下表：

模型	2D	\(\geq\)3D
无外场；随机铁磁相互作用	P	P
无外场；随机或均匀反铁磁相互作用	P	NPC
有均匀外场；均匀反铁磁相互作用	NPC	NPC
有随机外场；随机铁磁相互作用	P	P

表中随机反铁磁相互作用，即指 \(J_{ij}\) 取值可以不同符号。以上表格就完全解决了经典自旋系统的复杂度问题和分类。我们进一步的观察该表，透露出了几个事实：高维问题不比低维问题简单（废话），反铁磁问题不比对应的铁磁问题简单（这点在物理上比较有趣），最有趣的当属：无序问题不比均匀问题难。至少在我们研究的系统中，对应的无序版本模型和均匀相互作用的模型，复杂度上总是一致的。这背后是不是有深层次的原因，也值得思考。

factors make system NP hard

通过 RFIM 的复杂度的例子，可以更好的帮助我们认识什么特征的系统会NP完全，具体的说，这里就是打破临界温度非零和NP完全系统的联系。我们发现，是否在零温发生相变，对应的破缺后的态 energy landscape 更复杂，导致系统模拟变难之类的 argument 并不适用，具体结果见下表：

	\(T_c=0\)	\(T_c>0\)
P	\(d=2\) spin glass	ferro RFIM (\(d\geq 3\))
NPC	\(d=2+\epsilon\) spin glass	\(d\geq 3\) spin glass

其中的 \(d=2+\epsilon\) 的意思，就是指我们在经典自旋系统的-NP-完全中提到的两层方格子问题。从上表可知，有无有限温相变，和系统的复杂度无关。

what about disorder average

上面所说的问题的复杂度，都是指针对一个特定的无序构型，系统的基态能量是P或者NP完全。物理上关心的往往是 disorder average 之后的结果，这就引出了一个自然的问题，系统无序系综平均后的基态能量问题和单个无序构型的模型的基态能量问题复杂度相同吗？一方面，P 问题的 disorder average，朴素的看当然需要指数多的构型的结果平均。这样本来的P问题也有变的NP困难的可能性。但是，是否就像 Monte Carlo 的精神一样，事实上对多项式个无序构型求平均，就已经足够给出最后的结果了呢？另一方面，本来单个随机构型对应的基态能量是NP完全的问题，看起来毫无意外对不同构型求平均的结果更应该是NP完全的，但真的是这样吗。Anderson 最著名的 quote：More is different，似乎也有用在这里的可能性？虽然每个无序构型的问题都是困难的，但拨开重重迷雾，是否系综平均的结果反而是简单的呢，很多类似的物理图像告诉我们存在这种可能性，和这里最 relevant 的可能就是处理无序系统的 replica method。更进一步，这一问题可以直接推广到纯计算机科学领域，一个NP完全问题对应的优化问题当然是困难的，但如果求输入的某种平均下的优化问题呢？复杂度如何？

这一节的问题，我还没想到什么好的答案。但都说提出一个问题比解决一个问题更重要，那我就仅是暂将我的思考和疑问记录于此。

Sketch on Max Flow Algorithm

这节为了本文的完整性，略微记录一些 max flow min cut 定理和 max flow 算法的内容备忘，详细的证明和细节，可以参考 [3]。只希望有一些物理里启发的读者，本节可以直接略过。

首先我们需要利用 max flow min cut 定理，这个定理说的是从 s 到 t 的最大流，等于基于 st 两点分割的 min cut（最小割）。暴力点的话，通过把这两个问题写成线性规划问题，我们可以发现其是对偶的，因此得证。否则可以基于简单组合学和反证法证明，也不困难。这样基于两点的 min cut 问题就归约为了求 max flow 的问题。

如果只是想暴力证明 max flow 在P，考虑到 flow 变量的约束和优化，整个问题是一个连续变量的线性规划问题，因此一定在P （内点法解决LP具有 worst case 多项式的复杂度，参考[4]）。要想优雅一点，快速一点，则有著名的 Ford-Fulkerson 算法，及其改进版本 Edmonds-Karp 算法，可以将问题的复杂度控制在 \(O(\vert V\vert \vert E\vert^2)\)。当然后续还有更多理论上渐进更快的算法，详细列表可以参考wiki。Ford-Fulkerson 的算法其实想法很简单，就是将图上各边的权重做已有流量抵扣，余下的 residue graph，如果还有连同 s 和 t 的路径的话，就将流量沿路经增加路径上剩余 capacity 的最小值，如此循环，直到在 residue graph 上找不到通路。如果本来路径的寻找方式是 BFS，那就是 Edmonds-Karp 算法。比较困难的是这样做严格的正确性证明和复杂度分析，这里就不再赘述了。

Updates: 关于物理系统中计算复杂度的这一系列思考，我整理成了一篇文章，可以参考 arXiv:1911.04122.

Reference

1. J. C. Angles d’ Auriac, M. Preissmann, R. Rammal, The random field Ising model: algorithmic complexity and phase transition, J. Physique Lett. 46, 173(1985).
2. F. Hadlock, Finding a Maximum Cut of a Planar Graph in Polynomial Time, SIAM J. Comput. , 4(3), 221-225 (1975).
3. Charles E. Leiserson, Clifford Stein, Ronald Rivest, and Thomas H. Cormen, Introduction to Algorithms.
4. Leonid Khachiyan, A Polynomial Algorithm for Linear Programming, Doklady Akademii Nauk SSSR, 224 (5): 1093–1096 (1979).

EOF