[1] |
Cook S A.The complexity of theorem-proving procedures[C]∥Proc of the 3rd Annual ACM Symposium on Theory of Computing,1971:151-158.
|
[2] |
Kaporis A C,Kirousis L M,Stamatiou Y C,et al.The unsat- isfiability threshold revisited[J].Discrete Applied Mathematics,2007,155(12):81-95.
|
[3] |
Xu Dao-yun. Applications of minimal unsatisfiable formulas to polynomially reduction for formulas[J].Journal of Software,2006,17(5):1204-1212.(in Chinese)
|
[4] |
Franco J,Paull M.Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem[J].Discrete Applied Mathematics,1983,5(1):77-87.
|
[5] |
Mitchell D G,Selman B,Levesque H J.Hard and easy distributions of SAT problems[C]∥Proc of the 10th National Conference on Artificial Intelligence,1992:459-465.
|
[6] |
Kamath A P,Motwani R,Palem K V,et al.Tail bounds for occupancy and the satisfiability threshold conjecture[J].Random Structures & Algorithms,1994,7(1):59-80.
|
[7] |
Dubois O,Boufkhad Y.A general upper bound for the satisfiability threshold of random r-SAT formulae[J].Journal of Algorithms,1997,24(2):395-420.
|
[8] |
Kirousis L M, Kranakis E,Krizanc D,et al.Approximating the unsatisfiability threshold of random formulas[J].Random Structures & Algorithms,2015,12(3):253-269.
|
[9] |
Dubois O,Boufkhad Y,Mandler J.Typical random 3-SAT formulae and the satisfiability threshold[J].Electronic Colloquium on Computational Complexity,2003,10(7):1-2.
|
[10] |
Dubois O.Upper bounds on the satisfiability threshold[J].Theoretical Computer Science,2001,265(1-2):187-197.
|
[11] |
Kirousis L M, Stamatiou Y C,Zito M.The unsatisfiability threshold conjecture:Techniques behind upper bound improvements[M]∥Computational Complexity and Statistical Physics.New York:Oxford University Press,2005.
|
[12] |
Díaz J,Kirousis L,Mitsche D,et al.On the satisfiability threshold of formulas with three literals per clause[J].Theo- retical Computer Science,2009,410(30-32):2920-2934.
|
[13] |
Mézard M, Zecchina R. Random K-satisfiability problem:From an analytic solution to an efficient algorithm[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2002,66(5):56-126.
|
[14] |
Monasson R,Zecchina R.Statistical mechanics of the random K-SAT model[J].Physical Review E Statistical Physics Plasmas Fluids & Related Interdisciplinary Topics,1996,56(2):1357-1370.
|
[15] |
Achlioptas D,Chtcherba A D,Istrate G,et al.The phase transition in 1-i-nk SAT and NAE 3-SAT[C]∥Proc of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms,2001:721-722.
|
[16] |
Ding J, Sly A,Sun N.Satisfiability threshold for random regular NAE-SAT[J].Communications in Mathematical Physics,2016,341(2):435-489.
|
[17] |
Knysh S,Smelyanskiy V N,Morris R D.Approximating satisfiability transition by suppressing fluctuations[J].arXiv:cond-mat/0403416,2004.
|
[18] |
Kalapala V,Moore C.The phase transition in exact cover[J].arXiv:cs/0508037,2005.
|
[19] |
Moore C.The phase transition in random regular exact cover[J].arXiv:1502.07591,2015.
|
[20] |
Panagiotou K,Pasch M.Satisfiability thresholds for regular occupation problems[C]∥Proc of the 46th International Colloquium on Automata,Languages,and Programming,2019:1.
|
[21] |
Béla B. Random graphs[M].2nd Edition.Cambridge:Cambridge University Press,2001.
|
[22] |
Kirousis L M,Stamatiou Y C.An inequality for reducible,increasing properties of randomly generated words[R].Patras:Computer Technology Institute,University of Patras,1996.
|
[23] |
Alon N,Spencer J H.The probabilistic method[M].Manhattan:John Wiley & Sons,2004.
|
[24] |
Janson S.New versions of Suen’s correlation inequality[J].Random Structures & Algorithms,1998,13(3):467-483.
|
[25] |
Suen W C S.A correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph[J].Random Structures & Algorithms,1990,1(2):231-242.
|
[26] |
Knuth D E.The art of computer programming[M].London:Pearson Education,1997.
|
[27] |
Gasper G,Rahman M.Encyclopedia of mathematics and its applications[M].Cambridge:Cambridge University Press,1990.
|
[28] |
Kirousis L, Kranakis E,Krizanc D.An upper bound for a basic hypergeometric series:Technical Report TR-96-07[R].Ottawa:School of Computer Science,Carleton University,1996.
|
[29] |
Abramowitz M, Stegun I A.Handbook of mathematical function:with formulas,graphs,and mathematical tables[J].American Journal of Physics,1998,56(10):958.
|
|
附中文参考文献:
|
[3] |
许道云.极小不可满足公式在多项式归约中的应用[J].软件学报,2006,17(5):1204-1212.
|