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

摘要

本文首先构造了随机均匀产生的d-SAT问题的概率模型；然后给出了SAT问题的解的个数的均值的计算公式.使用矩方法研究了解空间的元素满足方程的概率以及在临界点方程有解的概率的极限性质.最后确定了n/m=γd=(ln2)/(ln22-1)是其解的平均个数的临界点，并且当n/m=γd时，方程有解的概率随着m→∞而趋于0.