主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2018年第5期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
周锦程,许道云,卢友军.随机正则(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)
作者单位E-mail
周锦程 贵州大学 计算机科学与技术学院, 贵州 贵阳 550025
黔南民族师范学院 数学与统计学院, 贵州 都匀 558000 
 
许道云 贵州大学 计算机科学与技术学院, 贵州 贵阳 550025 dyxu@gzu.edu.cn 
卢友军 贵州大学 计算机科学与技术学院, 贵州 贵阳 550025  
摘要点击次数: 814
全文下载次数: 828
中文摘要:
      研究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阅读器
 
主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利