|
|||||
|
|
The complexity of variable minimal formulas |
|
| Authors: | ZhenYu Chen BaoWen Xu DeCheng Ding |
| Institution: | 1 National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China; 2 Software Institute, Nanjing University, Nanjing 210093, China; 3 Department of Mathematics, Nanjing University, Nanjing 210093, China |
| Abstract: | 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 DP and coNP-hard. |
| Keywords: | minimal unsatisfiability prime implication variable minimal equivalence variable minimal satisfiability |
| 本文献已被 SpringerLink 等数据库收录！ | |
| 点击此处可从《中国科学通报(英文版)》浏览原始摘要信息 | |
| 点击此处可从《中国科学通报(英文版)》下载免费的PDF全文 | |