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
    /   /   推荐

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

首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录


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