Satisfiability threshold of the strictly d-regular random (3, s)-SAT problem
WANG Yong-ping, Daoyun Xu · 2020
the existing two models are modified to give SDRRKS model, where SDRRKS model generates strictly d-regular random (k, s)-CNF formulas. Let F be a strictly d-regular random (3, s)-CNF formula such that d fixes, then there exists a real number so such that F is unsatisfiable with high probability when s > so. The conclusion is consistent with the existing one when d is even. The simulated experiments in this paper verify the conclusion well. The research possibly helps generate random hard instances of the 3-SAT problem.