长程阻错的统计物理理论

一个无序自旋玻璃系统可能有许许多多能量最小态或基态构型．有些格点的自旋可能在所有这些基态中都只取同一个值（这种情况称为自旋凝固）．也有另外一种情况出现，即某些格点在一部分基态中自旋取向上而在其余的基态中自旋向下；这样的格点称为未凝固的格点．本文的工作表明，2个或多个未凝固的格点，虽然每个格点的自旋都随着基态的不同而改变，但是有可能某一些特定的自旋取向组合不会出现于任何一基态构型中．这种现象称为长程阻错．本文提出一个新的长程阻错序参量R来定量刻划这种现象，并将这一统计物理理论用于图的最小覆盖和K—SAT等组合优化问题．

A satistical physical theory of long range frustration

A spin glass system may have many configurations of the same ground-state energy. When the spins on some of the vertices have the same value among all the ground-state configurations, these vertices are referred to as frozen. If the spins on some other vertices have different values in different configurations, these vertices are therefore unfrozen. We show in this work that two or more unfrozen vertices may be prohibited from taking a certain combination of spin values, even though the spin of each vertex can fluctuate amongst different ground-state configurations. This phenomenon is called long-range frustration. We present a new long-range frustration order parameter R to quantify this phenomenon, and apply our mean field theory to the minimum vertex-cover problem and the random K-satisfiability problem.