 |
|
|
|
 |
 |
 |
|
 |
|
 |
|
|
| 周锦程,许道云,卢友军.随机正则(k,r)-SAT问题的可满足临界.软件学报,2016,27(12):2985-2993 |
| 随机正则(k,r)-SAT问题的可满足临界 |
| Satisfiability Threshold of the Regular Random (k,r)-SAT Problem |
| 投稿时间：2016-07-05 |
| DOI：10.13328/j.cnki.jos.005129 |
| 中文关键词: 随机正则(k,r)-SAT问题 可满足临界值 相变现象 计算复杂性 |
| 英文关键词:regular random (k,r)-SAT problem satisfiability threshold phase transition phenomena computational complexity |
| 基金项目:国家自然科学基金（61262006，61463044，61462001）；贵州省科技厅联合基金（LKQS201313） |
|
| 摘要点击次数: 1861 |
| 全文下载次数: 1810 |
| 中文摘要: |
| 研究k-SAT问题实例中每个变元恰好出现r=2s次，且每个变元对应的正、负文字都出现s次的严格随机正则（k，r）-SAT问题.通过构造一个特殊的独立随机实验，结合一阶矩方法，给出了严格随机正则（k，r）-SAT问题可满足临界值的上界.由于严格正则情形与正则情形的可满足临界值近似相等，因此得到了随机正则（k，r）-SAT问题可满足临界值的新上界.该上界不仅小于当前已有的随机正则（k，r）-SAT问题的可满足临界值上界，而且还小于一般的随机k-SAT问题的可满足临界值.因此，这也从理论上解释了在相变点处的随机正则（k，r）-SAT问题实例通常比在相应相变点处同规模的随机k-SAT问题实例更难满足的原因.最后，数值分析结果验证了所给上界的正确性. |
| 英文摘要: |
| This article studies the strictly regular (k,r)-SAT problem by restricting the k-SAT problem instances, where each variables occurs precisely r=2s times and each of the positive and negative literals occurs precisely s times. By constructing a special independent random experiment, the study derives an upper bound on the satisfiability threshold of the strictly regular random (k,r)-SAT problem via the first moment method. Based on the fact that the satisfiability threshold of the strictly regular and the regular random (k,r)-SAT problems are approximately equal, a new upper bound on the threshold of the regular random (k,r)-SAT problem is obtained. This new upper bound is not only below the current best known upper bounds on the satisfiability threshold of the regular random (k,r)-SAT problem, but also below the satisfiability threshold of the uniform random k-SAT problem. Thus, it is theoretically explained that in general the regular random (k,r)-SAT instances are harder to satisfy at their phase transition points than the uniform random k-SAT problem at the corresponding phase transition points with same scales. Finally, numerical results verify the validity of our new upper bound. |
|
HTML 下载PDF全文 查看/发表评论 下载PDF阅读器 |
|
|
|
|
|
|
 |
|
|
|
|
 |
|
 |
|
 |
|
