Please wait a minute...
 北京大学期刊网　|　作者　　审稿人　　编委专家　　工作人员 首页　  |  　关于　  |  　浏览　  |  　投稿指南　  |  　新闻公告
 数学进展
 研究论文
 可满足性(SAT)问题的概率研究 A Probabilistic Study on the Satisfiability Problem 张奎,陈大岳 Zhang Kui, Chen Dayue 北京大学数学科学学院概率统计系!北京,100871,中国,北京大学数学科学学院概率统计系!北京,100871,中国 (School of Math. Sciences, Peking Univ., Beijing, 100871, P. R. China 收稿日期: 2001-06-25 出版日期: 2001-06-25
 104 浏览 引用导出
0
/   /   推荐
 摘要 本文首先构造了随机均匀产生的ｄ－ＳＡＴ问题的概率模型；然后给出了ＳＡＴ问题的解的个数的均值的计算公式．使用矩方法研究了解空间的元素满足方程的概率以及在临界点方程有解的概率的极限性质．最后确定了ｎ／ｍ＝ｒｄ＝（ｌｎ２）／（ｌｎ（２ｄ／２ｄ－１） ）是其解的平均个数的临界点，并且当 ｎ／ｍ＝ｒｄ时，方程有解的概率随着ｍ→∞而趋于０． 关键词 ： SAT问题,  相变现象,  可满足概率 Abstract：We first define a probabilistic model for the d-satisfiability problem with each clause generated uniformly and randomly. Then we present a formula to compute the average number of solutions to a random d-satisfiability problem. We use the moment method to study the probability of an element of {0,1}m being a solution to a random d-satisfiability problem and the limit of the probability that a random d-satisfiability problem has a solution at the critical point, Finally we identity n/m =rd=(ln2)/(ln(2d/2d-1)) as the critical point of the average number of solutions to a random d-satisfiability problem. When n/m = rd, the probability that a random d-satisfiability problem has solutions goes to 0 as m→∞. Key words： phase transition    satisfiability probability
 No related articles found!
Viewed
Full text

Abstract

Cited

 © 2015-2017 北京大学图书馆 .