Cocco Simona, Monasson Rémi
CNRS-Laboratoire de Dynamique des Fluides Complexes, 3 rue de l'Université, 67000 Strasbourg, France.
Phys Rev E Stat Nonlin Soft Matter Phys. 2002 Sep;66(3 Pt 2B):037101. doi: 10.1103/PhysRevE.66.037101. Epub 2002 Sep 19.
A large deviation analysis of the solving complexity of random 3-satisfiability instances slightly below threshold is presented. While finding a solution for such instances demands an exponential effort with high probability, we show that an exponentially small fraction of resolutions require a computation scaling linearly in the size of the instance only. This exponentially small probability of easy resolutions is analytically calculated, and the corresponding exponent is shown to be smaller (in absolute value) than the growth exponent of the typical resolution time. Our study therefore gives some theoretical basis to heuristic stop-and-restart solving procedures, and suggests a natural cutoff (the size of the instance) for the restart.
本文给出了对略低于阈值的随机3 - 可满足性实例求解复杂度的大偏差分析。虽然以高概率找到此类实例的解需要指数级的努力，但我们表明，指数级小比例的归结仅需要与实例大小成线性比例的计算量。我们通过分析计算出了这种容易求解的指数级小概率，并且表明相应的指数（绝对值）小于典型求解时间的增长指数。因此，我们的研究为启发式的停止并重新开始求解过程提供了一些理论基础，并为重新开始提出了一个自然的截止点（实例的大小）。
