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)-CN...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.展开更多
基金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.
