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

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 +

PDF (435KB)

Cite this article

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 DOI:10.1007/s11704-022-1741-1

登录浏览全文

4963

注册一个新账户忘记密码

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