变量极小公式复杂性  

作　　者：陈振宇[1,2] 徐宝文[1] 丁德成[3] 

机构地区：[1]南京大学计算机软件新技术国家重点实验室,南京210093 [2]南京大学软件学院,南京210093 [3]南京大学数学系,南京210093

出　　处：《科学通报》2010年第12期1189-1193,共5页Chinese Science Bulletin

基　　金：国家自然科学基金(批准号:60803007,90818027和10871091);国家高技术研究发展计划(编号:2009AA01Z147);国家重点基础研究发展计划(编号:2009CB320703)资助项目

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

关 键 词：极小不可满足 基本蕴含数 变量极小等价 变量极小可满足 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]