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

Graphical abstract

References

[1] Fan Y, Shen J . On the phase transitions of random k-constraint satisfaction problems. Artificial Intelligence, 2011, 175( 3−4): 914–927

[2] Drori L, Peleg D. Faster solutions for exact hitting and exact SAT. Jerusalem: Weizmann Science Press of Israel, 1999

[3] Byskov J M, Madsen B A, Skjernaa B . New algorithms for Exact Satisfiability. Theoretical Computer Science, 2005, 332( 1−3): 515–541

[4] Moore C. The phase transition in random regular exact cover. Annales del' Institut Henri Poincare D 2016, 3(3): 349-362

[5] Mitzenmacher M, Upfal E. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge: University of Cambridge, 2005

Acknowledgements

This research was 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).

Competing interests

The authors declare that they have no competing interests or financial conflicts to disclose.

RIGHTS & PERMISSIONS

2024 Higher Education Press