变量极小公式复杂性

摘要：

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

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

所属期刊栏目：55

分类号：O1(数学)

资助基金：国家自然科学基金60803007;90818027和10871091;国家高技术研究发展计划2009AA01Z147;国家重点基础研究发展计划2009CB320703

在线出版日期：2011-05-17（万方平台首次上网日期，不代表论文的发表时间）

页码：1189-1193