可满足性(SAT)问题的概率研究

本文首先构造了随机均匀产生的ｄ－ＳＡＴ问题的概率模型；然后给出了ＳＡＴ问题的解的个数的均值的计算公式．使用矩方法研究了解空间的元素满足方程的概率以及在临界点方程有解的概率的极限性质．最后确定了ｎ／ｍ＝ｒｄ＝（ｌｎ２）／（ｌｎ（２ｄ／２ｄ－１） ）是其解的平均个数的临界点，并且当 ｎ／ｍ＝ｒｄ时，方程有解的概率随着ｍ→∞而趋于０．