随机k-SAT的相变上下界

李倩倩; 王以松; 冯仁艳; 张振鹏

首页> 中文期刊> 《贵州大学学报：自然科学版》 >随机k-SAT的相变上下界

随机k-SAT的相变上下界

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

在随机k-SAT模型的基础上,针对合取范式的满足性问题进行研究。对于固定的变量数n,随着子句数m增加,当m/n接近某一值时公式的可满足性发生剧烈的变化,可满足的概率从1变为0,也就是经常提到的相变问题。证明k-SAT相变的阈值上界为2kln2;当k(k0(ε是关于k的函数)且εn→!(趋近无穷大),存在α0=2~k ln2,使得下界为αl=(1-ε)α0。通过实验对k为2,3,4时的阈值进行验证。

著录项

来源
《贵州大学学报：自然科学版》 |2016年第5期|86-90|共5页
作者
李倩倩; 王以松; 冯仁艳; 张振鹏;
展开▼
作者单位

贵州大学计算机科学与技术学院;

展开▼
原文格式 PDF
正文语种 chi
中图分类理论、方法;
关键词
k-SAT; 可满足性; 相变; 阈值;

相似文献

中文文献
外文文献
专利

1. 关于随机MAX k-SAT模型的上界研究 [J] . 高宗升 ,许学琳 . 江西师范大学学报（自然科学版） . 2011,第002期
2. 随机k-SAT公式不可满足性VS最小k-击中集 [J] . 杨智应 . 计算机应用与软件 . 2009,第002期
3. 随机k-SAT问题的回溯算法分析 [J] . 许可 ,李未 . 计算机学报 . 2000,第005期
4. 关于不确定线性连续随机系统的协方差上下界研究 [J] . 王子栋 ,郭治 . 控制理论与应用 . 1996,第006期
5. 随机网络中三种渗流相变的交叉 [J] . 贾啸 ,王睿婕 ,张田 . 四川大学学报（自然科学版） . 2020,第005期
6. 非平稳随机响应的时变相变特性 [C] . 方同 . 中国力学会、中国航空学会第四届全国振动理论及应用学术会议 . 1990
7. 对随机系统中若干非平衡相变、粒子输运及随机共振现象的研究 [A] . 韩引霞 . 2005

随机k-SAT的相变上下界

摘要

著录项

相似文献

相关主题

期刊订阅