论文标题
复制对称性破坏了Ulam的问题
Replica symmetry breaking for Ulam's problem
论文作者
论文摘要
我们研究了由数字{1,2，...，n}置换给出的序列集合的增加子序列（IS）。我们考虑在温度t处的玻尔兹曼集合。因此，每个玻尔兹曼的概率都出现，其中能量是IS的负长度-l。对于t-> 0，只有基态，即最长的是（LIS）贡献，也称为Ulam的问题。我们引入了一种算法，该算法使我们能够直接采样在多项式时间内，对于任何给定的序列和任何温度，都处于完美的平衡。因此，我们可以研究非常大的尺寸。我们获得了$ n $的函数的第一和第二矩的平均值，并确认分析预测。此外，我们通过计算重叠的分布和执行分层群集分析来分析低温$ t $ t $。在热力学限制中，重叠的分布保持广泛，配置景观仍然很复杂。因此，乌拉姆的问题表现出复制对称性的破坏。这意味着它构成了具有复杂行为的模型，与其他RSB传播模型相比，可以以高效的方式进行数字研究，例如自旋玻璃或NP-HARD优化问题，在这些模型中尚无快速精确算法。
We study increasing subsequences (IS) for an ensemble of sequences given by permutation of numbers {1,2,...,n}. We consider a Boltzmann ensemble at temperature T. Thus each IS appears with the corresponding Boltzmann probability where the energy is the negative length -l of the IS. For T -> 0, only ground states, i.e. longest IS (LIS) contribute, also called Ulam's problem. We introduce an algorithm which allows us to directly sample IS in perfect equilibrium in polynomial time, for any given sequence and any temperature. Thus, we can study very large sizes. We obtain averages for the first and second moments of number of IS as function of $n$ and confirm analytical predictions. Furthermore, we analyze for low temperature $T$ the sampled ISs by computing the distribution of overlaps and performing hierarchical cluster analyses. In the thermodynamic limit the distribution of overlaps stays broad and the configuration landscape remains complex. Thus, Ulam's problem exhibits replica symmetry breaking. This means it constitutes a model with complex behavior which can be studied numerically exactly in a highly efficient way, in contrast to other RSB-showing models, like spin glasses or NP-hard optimization problems, where no fast exact algorithms are known.
