Computer Science ›› 2016, Vol. 43 ›› Issue (4): 33-36.doi: 10.11896/j.issn.1002-137X.2016.04.006
Previous Articles Next Articles
ZHANG Ming-ming and XU Dao-yun
| [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! |
|
||
Home