Satisfiability threshold of the random regular (s,c,k)-SAT problem

Xiaoling MO; Daoyun XU; Kai YAN; Zaijun ZHANG

doi:10.1007/s11704-022-1741-1

PDF(435 KB)

Front. Comput. Sci. ›› 2022, Vol. 16 ›› Issue (3) : 163408. DOI: 10.1007/s11704-022-1741-1

Theoretical Computer Science

LETTER

Satisfiability threshold of the random regular (s,c,k)-SAT problem

Author information +

History +

Cite this article

EndNote

Ris (Procite)

Bibtex

Download citation ▾

Xiaoling MO, Daoyun XU, Kai YAN, Zaijun ZHANG. Satisfiability threshold of the random regular (s,c,k)-SAT problem. Front. Comput. Sci., 2022, 16(3): 163408 https://doi.org/10.1007/s11704-022-1741-1

References

Publishing order | Descend order by publishing year | Descend order by cited within

[1]	Fu Z , Xu D . Uniquely satisfiable d-regular (k,s)-SAT instances. Entropy, 2020, 22( 5): 569

[2]	Wang Y , Xu D . Properties of the satisfiability threshold of the strictly d-regular random (3,2s)-SAT problem. Frontiers of Computer Science, 2020, 14( 6): 146404

[3]	Mitzenmacher M Upfal E. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. 2nd ed. Cambridge: Cambridge University Press, 2017

[4]	Flajolet P Sedgewick R. Analytic Combinatorics. Cambridge: Cambridge University Press, 2009

[5]	Boufkhad Y , Dubois O , Interian Y . Regular random k-SAT: properties of balanced formulas. Journal of Automated Reasoning, 2005, 35( 1−3): 181– 200

Acknowledgements

This research was funded by the National Natural Science Foundation of China (Grant Nos. 61762019, 61862051 and 62062001). The Science and Technology Foundation of Guizhou Province (Qian Ke Ping Tai Ren Cai [2019] QNSYXM-05).