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

• 作者: 张奎 陈大岳
• 来源期刊: 数学进展
• 学科: 数学
• 关键词: SAT问题 相变现象 可满足概率
• 年，卷（期）: 2001,（3）
• 页码范围: 231-237
• 页数: 7页
• 分类号: O21
• 字数: 4068字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-0917.2001.03.004

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈大岳	北京大学数学科学学院概率统计系	6	4	1.0	2.0
2	张奎	北京大学数学科学学院概率统计系	1	3	1.0	1.0