Computer Science ›› 2016, Vol. 43 ›› Issue (4): 33-36.doi: 10.11896/j.issn.1002-137X.2016.04.006

Previous Articles     Next Articles

Phase Transition Phenomenon of Regular 3-SAT Problem

ZHANG Ming-ming and XU Dao-yun   

  • Online:2018-12-01 Published:2018-12-01

Abstract: We considered the restriction on the 3-CNF formula on n Boolean variables{x1,x2,…,xn},in which each of the 2n literals occurs precisely {x1,x1,…,xn,xn} times.We called such formulas as regular (3,s)-CNF formulas.Through the two kinds of clauses generating mechanism of (3,s)-CNF formula,we observed that the regular (3,s)-CNF formulas are easier to be satisfied than non-regular 3-CNF formulas while the input size is small.Thus we inferred that compared with non-regular 3-SAT,the transition point of regular 3-SAT problems has offset phenomenon.Finally we explained this phenomenon from a perspective of the number of the variable’s degree of freedom.

Key words: Regular CNF formula,SAT problem,Phase transition,Variable’s degrees of freedom

[1] Kaporis A C,Kirousis L M,Lalas E G.The probabilistic analysis of a greedy satisfiability algorithm[J].Random Structures & Algorithms,2006,28(4):444-480
[2] Dubois O,Boufkhad Y,Mandler J.Typical random 3-SAT formulae and the satisfiability threshold [J/EB].arXiv:cs/0211036,2002
[3] Porschen S,Speckenmeyer E,Randerath B.On linear CNF formulas[M]∥Theory and Applications of Satisfiability Testing-SAT06.Seattle,WA,USA,Springer Berlin Heidelberg,2006:212-225
[4] Porschen S,Speckenmeyer E.NP-completeness of SAT for restricted linear formulas classes[C]∥Proceedings of the Symposium on Satisfiability in Logic-Based Modeling.Guangzhou,China,2006:108-121
[5] Porschen S,Speckenmeyer E,Zhao Xi-shun.Linear CNF formulas and satisfiability[J].Discrete Applied Mathematics,2009,157(5):1046-1068
[6] Tovey C A.A simplified NP-complete satisfiability problem[J].Discrete Applied Mathematics,1984,8(1):85-89
[7] Hoory S,Szeider S.Computing unsatisfiable k-SAT instances-with few occurrences per variables[J].Journal of Theoretical Computer Science,2005,337(1/3):347-359
[8] Hoory S,Szeider S.Families of unsatisfiable k-CNF formulaswith few occurrences per variables[J/EB].arXiv:math/0411167,4
[9] Savick  P,Sgall J.Note DNF tautologies with a limited number of occurrences of every variable[J].Theoretical Computer Science,2000,238(1/2):495-498
[10] Xu Dao-yun.Applications of minimal unsatisfiable formulas to polynomial reductions for formulas[J].Journal of Software,2006,17(5):1204-1212
[11] Xu Dao-yun,Deng Tian-yan,Zhang Qing-shun.k-LSAT is NP-complete for k≥3 [J].Journal of Software,2008,9(3):511-521
[12] Wang Jian,Xu Dao-yun.An effective algorithm for reducing k-CNF to t-CNF[J].Journal of Nanjing University(Mathematical Biquarterly),2005,22(1):53-65
[13] Jian Ding,Sly A,Sun N.Satisfiability threshold for random re-gular NAE-SAT[C]∥Proc.46th STOC.2014:814-822
[14] Coja-Oghlan A,Panagiotou K.Going after the k-SAT threshold[C]∥Proc.45th STOC.2013:705-714
[15] B Vapst,Coja-Oghlan A.The condensation phase transition in the regular k-SAT model[J/EB].arXiv:1507.035 12,2015

No related articles found!
Full text



No Suggested Reading articles found!