The complexity of variable minimal formulas
The complexity of variable minimal formulas
复制标题
DOI：
10.1007/s11434-010-3127-2
复制
发表时间：
2010-06
影响因子：
--
通讯作者：
Zhenyu Chen;Baowen Xu;Decheng Ding
中科院分区：
文献类型：
--
作者：
Zhenyu Chen;Baowen Xu;Decheng Ding
基于逻辑公式的共同性质：等价性和可满足性，引入了保持性质的变量极小公式的概念。一个公式是变量最小的，如果结果子公式与任何变量省略将改变给定的属性。研究了变量极小等价（VME）和变量极小可满足（VMS）两类问题的一些理论结果。我们证明了VME是NP-完全的，VMS是DP和coNP-困难的。
Based on the common properties of logic formulas: equivalence and satisfiability, the concept of variable minimal formulas with property preservation is introduced. A formula is variable minimal if the resulting sub-formulas with any variable omission will change the given property. Some theoretical results of two classes: variable minimal equivalence (VME) and variable minimal satisfiability (VMS) are studied. We prove that VME is NP-complete, and VMS is in DPand coNP-hard.