变量极小公式复杂性

陈振宇; 徐宝文; 丁德成

首页> 中文期刊> 《科学通报》 >变量极小公式复杂性

变量极小公式复杂性

开具论文收录证明 >>

文献代查 >>

文献数据库（团队版） >>

页面导航

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

摘要

基于逻辑公式的极小变量集合的需求,研究了变量极小等价(VME)和变量极小可满足(VMS)问题的理论性质.引入等价关键变量和可满足关键变量概念,证明它们的判定复杂性分别为NP-完全和DP-完全.通过等价关键变量和可满足关键变量,分别定义VME和VMS.证明了Unique-SATVMSVMESAT,其中Unique-SAT是具有唯一成真赋值的公式类.进一步证明VME是NP-完全,VMS属于DP且是coNP-难.

著录项

来源
《科学通报》 |2010年第12期|1189-1193|共5页
作者
陈振宇; 徐宝文; 丁德成;
展开▼
作者单位

南京大学计算机软件新技术国家重点实验室;

南京210093;

南京大学软件学院;

南京210093;

南京大学数学系;

南京210093;

展开▼
原文格式 PDF
正文语种 chi
中图分类算法理论;
关键词
极小不可满足; 基本蕴含数; 变量极小等价; 变量极小可满足;

相似文献

中文文献
外文文献
专利

1. 可满足公式到极小不可满足公式MU(1)的扩张复杂性 [J] . 张庆顺 ,许道云 . 贵州大学学报（自然科学版） . 2005,第4期
2. 一个极小不可满足公式子类改名的复杂性研究 [J] . 陈庆燕 . 滨州学院学报 . 2011,第6期
3. 一种基于消解的变量极小不可满足子公式的提取方法 [J] . 陈振宇 ,徐宝文 ,周从华 . 计算机研究与发展 . 2008,第z1期
4. 极小曲面与复杂性节点"FLORA"艺术装置项目 [J] . 赵阳臣1 . 中华建设 . 2019,第5期
5. 熵极小动力系统的复杂性 [J] . 尹建东 ,周作领 . 数学物理学报 . 2015,第1期
6. 一种基于消解的变量极小不可满足子公式的提取方法 [C] . 陈振宇 ,徐宝文 ,周从华 . 2007全国理论计算机科学学术年会 . 2007
7. 极小不可满足公式在CNF公式类归约中的应用 [A] . 王健 . 2005

变量极小公式复杂性

摘要

著录项

引文网络

相似文献

相关主题

期刊订阅