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

来源：软件学报杂志2021年第9期北京时间：

作者：王永平，许道云

单位：王永平，贵州大学计算机科学与技术学院, 贵州 贵阳 550025;贵州财经大学 数统学院, 贵州 贵阳 55002511,许道云，贵州大学计算机科学与技术学院, 贵州 贵阳 55002502

摘要：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

关键词：3-CNF公式;随机难解实例生成;正则子类;严格d-正则随机(3,2s)-SAT问题;可满足临界

基金资助：国家自然科学基金（61762019，61862051）