Researchers find the conditions which make a regular balanced random (k,2s)-CNF formula (1,0)-unsatisfiable with high probability. The conditions also make a random instance of the regular balanced (k-1,2(k-1)s)-SAT problem unsatisfiable with high probability, where the instance obeys a distribution which differs from the distribution obeyed by a regular balanced random (k-1,2(k-1)s)-CNF formula. So, the researchers actually provide a class of new random instances for designing algorithms for the k-SAT problem. The findings were published on 15 August 2024 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
Frontiers of Computer Science
Experimental study
Not applicable
On the upper bounds of (1,0)-super solutions for the regular balanced random (k,2s)-SAT problem
15-Aug-2024