Exact satisfiability and phase transition analysis of the regular(k,d)-CNF formula  

作　　者：Guoxia NIE Daoyun XU Xi WANG Zaijun ZHANG 

机构地区：[1]College of Computer Science and Technology,Guizhou University,Guiyang 550025,China [2]School of Mathematics and Statistics,Qiannan Normal University for Nationalities,Duyun 558000,China [3]Key Laboratory of Industrial Automation and Machine Vision of Qiannan,Duyun 558000,China

出　　处：《Frontiers of Computer Science》2024年第1期263-265,共3页中国计算机科学前沿（英文版）

基　　金：funded by the National Natural Science Foundation of China(Grant Nos.61862051,62241206 and 62062001);the Science and Technology Plan Project of Guizhou Province(Grant No.Qiankehe Foundation-ZK[2022]General 550).

摘　　要：1Introduction The satisfiability(SAT)problem has been considered the"seed"of other NP-complete problems.The regular partial exact(k,d)-SAT problem is an important extension of the SAT problem.For any(k,d)-CNF formula with a variable set V,V'is a proper subset of V,the problem involves determining whether a truth assignment set on V'exists such that only a literal in each clause is true.When V'=V,it is a regular exact(k,d)-SAT problem.Currently,both experimental verifications and theoretical analyses of k-SAT problem have shown that the ratioα(clause constraint density)of the number of clauses m to the number of variables n is an important parameter affecting the satisfiability of the formula[1].However,the regular(k,d)-SAT problem has the same clause constraint density d/k.

关 键 词：FORMULA constraint EXACT 

分 类 号：O211.6[理学—概率论与数理统计]