| 关于随机MAX k-SAT模型的上界研究 |
| |
| 引用本文： | 高宗升,许学琳.关于随机MAX k-SAT模型的上界研究[J].江西师范大学学报(自然科学版),2011,35(2):111-115. |
| |
| 作者姓名： | 高宗升 许学琳 |
| |
| 作者单位： | 数学、信息与行为教育部重点实验室,北京航空航天大学数学与系统科学学院,北京,100191 |
| |
| 基金项目： | 国家自然科学基金，中央高校基本科研业务费专项资金资助项目 |
| |
| 摘 要： | 对于包含n个变量和m=αn个长度为k的子句的CNF公式,人们比较关注公式中最大可满足子句的个数max Fk(MAX k-SAT).当子句密度α比较大时,随机MAX k-SAT模型中的变量f k(n,αn)E(max Fk)的上界可以用一阶矩方法给出.通过对一阶矩方法放缩精度的改进,得到了它的一个更紧的上界(1-1/2 k)αn+h(α,t)·αn.同时,可以证明这个新的上界随着t的增大而变得更紧.
|
| 关 键 词： | MAX k-SAT 上界 一阶矩方法 |
The Upper Bound Research for Random MAX k-SAT |
| |
| GAO Zong-sheng,XU Xue-lin.The Upper Bound Research for Random MAX k-SAT[J].Journal of Jiangxi Normal University (Natural Sciences Edition),2011,35(2):111-115. |
| |
| Authors: | GAO Zong-sheng XU Xue-lin |
| |
| Institution: | GAO Zong-sheng,XU Xue-lin(LMIB & School of Mathematics and Systems Science,Beijing University of Aeronautics and Astronautics,Beijing 100191,China) |
| |
| Abstract: | |
| |
| Keywords: | MAX k-SAT |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
