期刊导航
期刊开放获取
河南省图书馆
退出
期刊文献
+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
检索
高级检索
期刊导航
共找到
1
篇文章
<
1
>
每页显示
20
50
100
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
显示方式:
文摘
详细
列表
相关度排序
被引量排序
时效性排序
取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界
被引量:
1
1
作者
王永平
许道云
《软件学报》
EI
CSCD
北大核心
2021年第9期2629-2641,共13页
3-CNF公式的随机难解实例生成对于揭示3-SAT问题的难解实质和设计满足性测试的有效算法有着重要意义.对于整数k>2和s>0,如果在一个k-CNF公式中每个变量正负出现次数均为s,则称该公式是严格正则(k,2s)-CNF公式.受严格正则(k,2s)-CN...
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取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.
展开更多
关键词
3-CNF公式
随机难解实例生成
正则子类
严格d-
正则
随机(3
2s)-SAT问题
可满足临界
下载PDF
职称材料
题名
取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界
被引量:
1
1
作者
王永平
许道云
机构
贵州大学计算机科学与技术学院
贵州财经大学数统学院
出处
《软件学报》
EI
CSCD
北大核心
2021年第9期2629-2641,共13页
基金
国家自然科学基金(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取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.
关键词
3-CNF公式
随机难解实例生成
正则子类
严格d-
正则
随机(3
2s)-SAT问题
可满足临界
Keywords
3-CNF formula
generating random hard instances
subclass with regular structure
strictly d-regular random(3,2s)-SAT problem
satisfiability threshold
分类号
TP301 [自动化与计算机技术—计算机系统结构]
下载PDF
职称材料
题名
作者
出处
发文年
被引量
操作
1
取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界
王永平
许道云
《软件学报》
EI
CSCD
北大核心
2021
1
下载PDF
职称材料
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
上一页
1
下一页
到第
页
确定
用户登录
登录
IP登录
使用帮助
返回顶部