极小不可满足公式

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

检索结果分析

结果分析中...
选择条件：
  • 期刊=软件学报x
共 条 记 录，以下是1-3
全选清除导出
参考文献引证文献引用追踪
视图：
排序：
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(1)和MARG(1)中公式改名的复杂性(英文)被引量：3
《软件学报》2006年第7期1517-1526,共10页许道云 董改芳 王健 
国家自然科学基金;贵州省高层次人才科研条件特助经费;贵州省省长基金~~
改名是一个将变元映射到变元本身或它的补的函数,变元改名是公式变元集合上的一个置换,文字改名是一个改名和一个变元改名的组合.研究CNF公式的改名有助于改进DPLL算法.考虑判定问题“对于给定的CNF公式H和F是否存在一个变元(或文字)改...
关键词：计算复杂性 改名 极小不可满足公式 
极小不可满足公式在多项式归约中的应用被引量：24
《软件学报》2006年第5期1204-1212,共9页许道云 
国家自然科学基金;贵州省高层次人才科研条件特助基金;贵州省省长基金~~
合取范式(CNF)公式F是极小不可满足的,如果F不可满足,并且从F中删去任意一个子句后得到的公式可满足,(r,s)-CNF是限制CNF公式中每个子句恰有r个不同的文字,且每个变元出现的次数不超过s次的公式类,对应的满足性问题(r,s)-SAT指实例公式...
关键词：极小不可满足公式 问题 多项式归约 NP-完全 公式构造 
全选清除导出
共1页<1>
检索报告 对象比较 聚类工具 使用帮助 返回顶部