摘要： 通过对3-CNF公式加以限制,要求其中每个变元出现的次数相同,引出正则3-SAT问题。进一步,通过对两种子句产生机制形成的(3,s)-CNF公式进行可满足性观察,发现在规模较小的情况下,正则3-CNF公式比非正则3-CNF公式更容易满足。从而推测与非正则3-SAT问题相比,正则3-SAT问题的相变点有偏移现象。最后,从变元自由度的角度对这一现象给出了定性解释。
| [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! |
|
||
首页