取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界
作者:
作者单位:

作者简介:

王永平(1980-),男,讲师,主要研究领域为计算复杂性,可计算性分析.
许道云(1959-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为计算复杂性,可计算性分析.

通讯作者:

许道云,E-mail:dyxu@gzu.edu.cn

基金项目:

国家自然科学基金(61762019,61862051)


Satisfiability Threshold of Strictly d-regular Random (3,2s)-SAT Problem for Fixed s
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61762019, 61862051)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
    摘要:

    3-CNF公式的随机难解实例生成对于揭示3-SAT问题的难解实质和设计满足性测试的有效算法有着重要意义.对于整数k>2和s>0,如果在一个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取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.

    Abstract:

    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, the strictly d-regular (k,2s)-CNF formula is proposed in which the absolute value of the difference between positive and negative occurrence number of every variable is d. A novel model is constructed to generate the strictly d-regular random (k,2s)-CNF formula. The simulated experiments show that the strictly d-regular random (3,2s)-SAT problem has an SAT-UNSAT phase transition and a HARD-EASY phase transition when the parameter 5<s<11 is fixed, and that the latter is related to the former. Hence, the satisfiability threshold of the strictly d-regular random (3,2s)-SAT problem is studied when the parameter s is fixed. A lower bound of the satisfiability threshold is obtained by constructing a random experiment and using the first moment method. The subsequent simulated experiments verify well the lower bound proved.

    参考文献
    相似文献
    引证文献
引用本文

王永平,许道云.取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界.软件学报,2021,32(9):2629-2641

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
历史
  • 收稿日期:2019-03-22
  • 最后修改日期:2019-11-28
  • 录用日期:
  • 在线发布日期: 2020-05-26
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号