《计算机工程与科学杂志》发表论文赏析

多文字可满足SAT问题的相变点上界

来源:计算机工程与科学杂志2022年第7期北京时间:

作者:芦磊, 王晓峰, 梁晨, 张九龙

单位:1.北方民族大学计算机科学与工程学院,宁夏 银川 750021;2.北方民族大学图像图形智能处理国家民委重点实验室,宁夏 银川 750021

摘要:可满足(SAT)问题是指:是否存在一组布尔变元赋值,使得随机合取范式(CNF)公式中每个子句至少有1个文字为真。多文字可满足SAT问题是指:是否存在一组布尔变元赋值,使得随机CNF公式中每个子句至少有2个文字为真。此问题仍然是一个NP难问题。定义约束密度α为CNF公式子句数与变元数之比,对该问题的相变点上界α*进行了研究。如果α>α*,则多文字可满足SAT问题高概率不可满足。通过一阶矩一个简单的推断,可以证明α*=-ln 2/ln(1-(k+1)/2k),当k=3时,α*=1。利用Kirousis等人的局部最大值技术,提升了多文字可满足3-SAT问题的相变点上界α*=0.7193。最后,选择了大量数据进行实验验证,结果表明,理论结果与实验结果相吻合。

关键词:多文字可满足,SAT问题,不满足阈值,相变点上界,合取范式,

基金资助:国家自然科学基金(62062001,61762019,61862051,61962002);北方民族大学创新项目(YCX21083);宁夏自然科学基金(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119)

2022年7期其他文献查阅:

面向Flink的负载均衡任务调度算法的研究与实现

基于MPI的并行大数据集生成器

国产通用处理器密码算法指令实现研究

多路系统Cache一致性验证中的错误追踪定位技术

基于NR-Transformer的集群作业运行时间预测

一种面向分布式深度学习的轻量级聚合通信库

小信号放大电路任意波形THD全自动测量系统研究

一种基于聚类与噪声的网络流量分类方法

无人机辅助的无线传感网络AoI最小化方案研究

基于多智能体的海外反恐运输投送模型研究

基于雾计算面向停车服务的隐私保护方案

基于特征通道和空间位置注意力的三维点云特征学习网络

面向点云三维重建的空间感知对抗神经网络

基于区域划分和四元数的彩色图像复制粘贴篡改检测

基于轻量级神经网络的目标检测研究

基于改进A*算法和动态窗口法的机器人路径规划

多文字可满足SAT问题的相变点上界

面向公平保障的共乘定价与匹配算法

一种基于CSI的高鲁棒性步态识别方法

基于多重相关信息交互的文本相似度计算方法

随机约束满足问题相变研究综述

填文献完整题目 获取完整文献

填写需求
联系方式
注:学术顾问会在1小时内联系您,请留意!