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

RIGHTS & PERMISSIONS

Higher Education Press