随机正则( k, r )-SAT问题的可满足临界

周锦程、Jincheng Zhou、许道云、Daoyun Xu、卢友军、Lu Youjun

2016Mathematics被引 1

摘要

研究k-SAT问题实例中每个变元恰好出现r=2s次，且每个变元对应的正、负文字都出现s次的严格随机正则（k，r）-SAT问题.通过构造一个特殊的独立随机实验，结合一阶矩方法，给出了严格随机正则（k，r）-SAT问题可满足临界值的上界.由于严格正则情形与正则情形的可满足临界值近似相等，因此得到了随机正则（k，r）-SAT问题可满足临界值的新上界.该上界不仅小于当前已有的随机正则（k，r）-SAT问题的可满足临界值上界，而且还小于一般的随机k-SAT问题的可满足临界值.因此，这也从理论上解释了在相变点处的随机正则（k，r）-SAT问题实例通常比在相应相变点处同规模的随机k-SAT问题实例更难满足的原因.最后，数值分析结果验证了所给上界的正确性.

引用本文（GB/T 7714）

周锦程, Jincheng Zhou, 许道云, 等. 随机正则( k, r )-SAT问题的可满足临界[J]. 未知来源, 2016.

引文网络

参考文献与被引分析加载中…

DOI：https://doi.org/10.13328/j.cnki.jos.005129

本站仅收录题录与摘要供学习参考，全文版权归属出版方；如有侵权请联系我们删除。