主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第9期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
王永平,许道云.取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界.软件学报,0,(0):0
取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界
Satisfiability Threshold of the Strictly d-Regular Random (3,2s)-SAT Problem for Fixed s
投稿时间:2019-03-22  修订日期:2019-11-28
DOI:10.13328/j.cnki.jos.006049
中文关键词:  3-CNF公式  随机难解实例生成  正则子类  严格d-正则随机(3,2s)-SAT问题  可满足临界
英文关键词:3-CNF formula  generating random hard instances  subclass with regular structure  strictly d-regular random (3,2s)-SAT problem  satisfiability threshold
基金项目:国家自然科学基金(61762019,61862051)
作者单位E-mail
王永平 贵州大学 计算机科学与技术学院, 贵州 贵阳 550025
贵州财经大学 数统学院, 贵州 贵阳 550025 
 
许道云 贵州大学 计算机科学与技术学院, 贵州 贵阳 550025 dyxu@gzu.edu.cn 
摘要点击次数: 239
全文下载次数: 224
中文摘要:
      3-CNF公式的随机难解实例生成对于揭示3-SAT问题的难解实质和设计满足性测试的有效算法有着重要意义.对于整数k>2和s>2如果在一个k-CNF公式中每个变量正负出现次数均为s,则称该公式是严格正则(k,2s)-CNF公式.受严格正则(k,2s)-CNF公式的结构特征启发,提出每个变量正负出现次数之差的绝对值均为d的严格d-正则(k,2s)-CNF公式,并使用新提出的SDRRK2S模型生成严格d-正则随机(k,2s)-CNF公式.取定整数5 < s < 11模拟实验显示,严格d-正则随机(3,2s)-SAT问题存在SAT-UNSAT相变现象和HARD-EASY相变现象.因此,立足于3-CNF公式的随机难解实例生成,研究了严格d-正则随机(3,2s)-SAT问题在s取定时的可满足临界.通过构造一个特殊随机试验和使用一阶矩方法得到了严格d-正则随机(3,2s)-SAT问题在s取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.
英文摘要:
      Generating random hard instances of the 3-CNF formula is an important factor in revealing the intractability of the 3-SAT problem and designing effective algorithms for satisfiability testing. Let k > 2 and s > 0 be integers, a k-CNF formula is a strictly regular (k, 2s)-CNF one if the positive and negative occurrence number of every variable in the formula are s. On the basis of the strictly regular (k, 2s)-CNF formula, we propose the strictly d-regular (k, 2s)-CNF formula in which the absolute value of the difference between positive and negative occurrence number of every variable is d. We construct a novel model to generate the strictly d-regular random (k, 2s)-CNF formula. Our simulated experiments show that the strictly d-regular random (3, 2s)-SAT problem has an SAT-UNSAT phase transition and an HARD-EASY phase transition when the parameter 5 < s < 11 is fixed, and that the latter is related to the former. Hence, we study the satisfiability threshold of the strictly d-regular random (3, 2s)-SAT problem when the parameter s is fixed. We obtain a lower bound of the satisfiability threshold by constructing a random experiment and using the first moment method. The subsequent simulated experiments verify well the lower bound proved by us.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利