极小不可满足公式在多项式归约中的应用

许道云

首页> 中文期刊> 《软件学报》 >极小不可满足公式在多项式归约中的应用

极小不可满足公式在多项式归约中的应用

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

合取范式(CNF)公式F是极小不可满足的,如果F不可满足,并且从F中删去任意一个子句后得到的公式可满足,(r,s)-CNF是限制CNF公式中每个子句恰有r个不同的文字,且每个变元出现的次数不超过s次的公式类,对应的满足性问题(r,s)-SAT指实例公式限制于(r,s)-CNF.对于正整数r≥3,有一个临界函数f(r),使得(r,f(r))-CNF中的公式都是可满足的,而(r,f(r)+1)-SAT却是NP-完全的.函数f是否可计算是一个开问题,除了知道f(3)=3,f(4)=4外,只能估计f(r)的界.描述了极小不可满足公式在CNF公式类之间转换中的作用.为使转换过程中引入较少的新变元,给出了CNF公式到3-CNF公式的一种新的转换方法,对于长度为l(＞3)的子句,仅需引入|l/2|个新变元.并且,给出了CNF到(r,s)-CNF公式转换以及(r,s)-CNF中不可满足公式构造的原理和方法.

著录项

来源
《软件学报》 |2006年第5期|1204-1212|共9页
作者
许道云;
展开▼
作者单位

贵州大学;

计算机科学系;

贵州;

贵阳;

550025;

展开▼
原文格式 PDF
正文语种 chi
中图分类人工智能理论;
关键词
极小不可满足公式; 问题; 多项式归约; NP-完全; 公式构造;

相似文献

中文文献
外文文献
专利

1. 可满足公式到极小不可满足公式MU(1)的扩张复杂性 [J] . 张庆顺 ,许道云 . 贵州大学学报（自然科学版） . 2005,第004期
2. 一个极小不可满足公式子集的构造 [J] . 陈庆燕 ,姚雷博 . 洛阳理工学院学报（自然科学版） . 2011,第004期
3. 一个极小不可满足公式子类改名的复杂性研究 [J] . 陈庆燕 . 滨州学院学报 . 2011,第006期
4. 一种寻找极小不可满足子公式的方法 [J] . 李立峰 . 西安邮电学院学报 . 2009,第005期
5. 一种基于消解的变量极小不可满足子公式的提取方法 [J] . 陈振宇 ,徐宝文 ,周从华 . 计算机研究与发展 . 2008,第0z1期
6. 一种基于消解的变量极小不可满足子公式的提取方法 [C] . 陈振宇 ,徐宝文 ,周从华 . 2007全国理论计算机科学学术年会 . 2007
7. 极小不可满足公式在CNF公式类归约中的应用 [A] . 王健 . 2005

极小不可满足公式在多项式归约中的应用

摘要

著录项

相似文献

相关主题

期刊订阅