变量极小公式复杂性

作者：陈振宇; 徐宝文; 丁德成

来源：科学通报, 2010, (12): 1189-1193.

• 极小不可满足
• 基本蕴含数
• 变量极小等价
• 变量极小可满足

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

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