Some variants of SAT and their properties  

作　　者：ZHAO Yunlei and ZHU Hong(1. Department of Computer Science, Fudan University, Shanghai 200433, China 2. Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong) 

出　　处：《Progress in Natural Science:Materials International》2002年第10期789-793,共5页自然科学进展·国际材料（英文版）

基　　金：Supported by the National Natural Science Foundation of China (Grant No. 69973013)

摘　　要：A new model for the well-known problem, the satisfiablility problem of boolean formula (SAT), is introduced. Based on this model, some variants of SAT and their properties are presented. Denote by NP the class of all languages which can be decided by a non-deterministic polynomial Turing machine and by P the class of all languages which can be decided by a deterministic polynomial-time Turing machine. This model also allows us to give another candidate for the natural problems in ((NP-NPC)-P), denoted as NPI, under the assumption P≠NP, where NPC represents NP-complete. It is proven that this candidate is not in NPC under P≠NP. While, it is indeed in NPI under some stronger but reasonable assumption, specifically, under the Exponential-Time Hypothesis (ETH). Thus we can partially solve this long standing important open problem.A new model for the well-known problem, the satisfiability problem of boolean formula (SAT), is introduced. Based on this model, some variants of SAT and their properties are presented. Denote by NP the class of all languages which can be decided by a non-deterministic polynomial Turing machine and by P the class of all languages which can be decided by a deterministic polynomial-time Turing machine. This model also allows us to give another candidate for the natural problems in ((NP-NPC)-P), denoted as NPI, under the assumption P≠NP, where NPC represents NP-complete. It is proven that this candidate is not in NPC under P≠NP. While, it is indeed in NPI under some stronger but reasonable assumption, specifically, under the Exponential-Time Hypothesis (ETH) . Thus we can partially solve this long standing important open problem.

关 键 词：NP-COMPLETE Karp-reduction SAT ETH NPI SNP. 

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