论文部分内容阅读
3SAT问题有一个非常奇妙的相变现象.对于固定的变量数N,合取范式的可满足概率随着子句数K的变化而发生剧烈的变化,当K≈4.3*N时,可满足概率急剧地从1变为0.相变现象决定了问题的难易分布,对于快速求解算法的设计有着非常重要的意义. 在文献中,我们着重从宏观的角度,用回归分析的方法逼近相变曲线,进而求得两个重要的参数α和β.本文从统计的角度对3SAT问题的相变现象进行描述,更深刻地揭示出相变的实质.
The 3SAT problem has a very fantastic phase change phenomenon. For a fixed number of variables N, the satisfiability probability of the inclusion paradigm changes drastically with the number of clauses K. When K≈4.3 * N, the probability Rapidly changing from 1 to 0. The phenomenon of phase change determines the easy distribution of the problem and is of great significance for the design of a fast solution algorithm.In the literature, we focus on the macro-level approach of regression analysis to approach the phase transition Curve, and then obtain two important parameters α and β.This paper describes the phenomenon of phase transition of 3SAT from a statistical point of view, reveals the essence of the phase transition.