极小不可满足公式

作品数：18被引量：33H指数：3
导出分析报告
相关领域：自动化与计算机技术理学更多>>
相关作者：许道云徐小萍陈庆燕张庆顺王健更多>>
相关机构：贵州大学南京大学襄樊学院滨州学院更多>>
相关期刊：《软件学报》《计算机科学与探索》《井冈山大学学报（自然科学版）》《洛阳理工学院学报（自然科学版）》更多>>
相关基金：国家自然科学基金贵州省省长基金贵州省高层次人才科研条件特助经费项目国家高技术研究发展计划更多>>
-
在结果中检索

检索结果分析

结果分析中...
共 条 记 录，以下是1-10
全选清除导出
参考文献引证文献引用追踪
视图：
排序：
用于求解正则(3,4)-SAT实例集的修正警示传播算法被引量：2
《计算机科学》2018年第11期312-317,共6页佘光伟 许道云 
国家自然科学基金项目(61762019;61462001)资助
利用极小不可满足公式的临界特性,可以将任意的一个3-CNF公式多项式时间归约转换为一个正则(3,4)-CNF公式,从而得到一个保留NP完全性的正则(3,4)-SAT问题。警示传播算法(Warning Propagation,WP)在归约转换后的正则(3,4)-SAT实例集上高...
关键词：极小不可满足公式 正则(3 4)-SAT问题 警示传播算法 
一个极小不可满足公式子集的构造
《洛阳理工学院学报（自然科学版）》2011年第4期77-79,87,共4页陈庆燕 姚雷博 
滨州学院青年人才创新基金(BZXYQNLG200611)
对于极小不可满足公式和它的子类的研究是近年来兴起的一个热门方向。极小不可满足公式通过分裂得到的公式保持了极小不可满足性,它的子类的某些性质对于建立在分裂上的归纳证明是很有用的。找到了一个能递归构造的极小不可满足公式的子...
关键词：极小不可满足公式 MAX+(k)公式集 分裂对 
一个极小不可满足公式子类改名的复杂性研究
《滨州学院学报》2011年第6期82-85,共4页陈庆燕 
滨州学院青年人才创新工程科研基金项目(BZXYQNLG200611)
改名规则在创建有效的满足性算法和简化某些消解难例的证明中起到了重要作用,对于一些具有对称结构的难例公式,可以通过改名来降低其证明的复杂性.研究了一个极小不可满足公式子类,给出了该子类的改名算法,并证明了对该子类中改名问题...
关键词：改名 极小不可满足公式 子类 多项式时间 
极小不可满足核及其提取
《廊坊师范学院学报（自然科学版）》2011年第5期14-15,共2页徐小萍 
在极小不可满足公式和可满足公式的基础上给出极小不可满足核的定义,并给出用布尔可满足求解器提取不可满足公式的极小不可满足核的方法。
关键词：极小不可满足公式 提取 求解器 
MAX-k-SAT的PTAS归约等价性
《计算机科学与探索》2009年第6期641-648,共8页许道云 秦永彬 
国家自然科学基金~~
通过构造适当的极小不可满足公式,利用子句拼接技术,引入了一个一般化的从k-CNF公式(k≥3)到3-CNF公式之间的归约转换。基于该转换,给出了一个真值指派的转换算法,并证明了MAX-k-SAT与MAX-3-SAT是PTAS归约等价的。因此,对于k,t≥3,MAX-k...
关键词：极小不可满足公式 归约 MAX—k—SAT问题 PTAS等价 
MARG-MU(2)的结构和复杂度
《井冈山大学学报（自然科学版）》2009年第2期30-33,共4页徐小萍 
SAT问题(可满足性问题)是理论计算机科学的核心问题,研究SAT问题的方法很多,利用极小不可满足公式的性质来研究SAT问题是近几年兴起的一个热点研究方向。本文主要利用(1,*)-消解方法研究了差为2的边缘极小不可满足公式集(MARG-MU(2))的...
关键词：极小不可满足公式 可满足性问题 边缘 消解 
集合MU的某些子类间的包含关系
《襄樊学院学报》2008年第8期11-14,39,共5页徐小萍 
通过具体公式在增加或删去某些文字或子句后生成的新公式的可满足性来研究极小不可满足公式类的常见子类Dis-MU,HIT-MU,Unique-MU,MARG-MU,MAX-MU和SYM-MU之间的包含关系.
关键词：极小不可满足公式 真值指派 包含关系 
k-LSAT(k≥3)是NP-完全的(英文)被引量：5
《软件学报》2008年第3期511-521,共11页许道云 邓天炎 张庆顺 
Supported by the National Natural Science Foundation of China under Grant Nos.10410638, 60310213 (国家自然科学基金)
合取范式(conjunctive normal form,简称CNF)公式F是线性公式,如果F中任意两个不同子句至多有一个公共变元.如果F中的任意两个不同子句恰好含有一个公共变元,则称F是严格线性的.所有的严格线性公式均是可满足的,而对于线性公式类LCNF,...
关键词：线性CNF公式 不可满足性 NP-完全性 极小不可满足公式 归约 
MAX和MARG中公式改名的复杂性(英文)
《南京大学学报（数学半年刊）》2006年第2期181-199,共19页许道云 
Supported by the National Natural Science Foundation of China (No. 60463001,No. 10410638, No. 60310213).
研究了判定问题“对于命题CNF公式F和H,是否存在一个变元(或文字)改名(?),使得(?)(F)=H?”的复杂性．对于极小不可满足公式的子类MAX和MARG,我们证明了:其变元改名和文字改名的复杂性等价于图同构问题GI．
关键词：复杂性 变元改名 文字改名 极小不可满足公式 图同构 
MAX(1)和MARG(1)中公式改名的复杂性(英文)被引量：3
《软件学报》2006年第7期1517-1526,共10页许道云 董改芳 王健 
国家自然科学基金;贵州省高层次人才科研条件特助经费;贵州省省长基金~~
改名是一个将变元映射到变元本身或它的补的函数,变元改名是公式变元集合上的一个置换,文字改名是一个改名和一个变元改名的组合.研究CNF公式的改名有助于改进DPLL算法.考虑判定问题“对于给定的CNF公式H和F是否存在一个变元(或文字)改...
关键词：计算复杂性 改名 极小不可满足公式 
全选清除导出
共2页<12>
检索报告 对象比较 聚类工具 使用帮助 返回顶部