On state space structure and average case complexity in random K-SAT problems
作者： John Ardelius
DOI:
关键词:
摘要: This thesis gives an introduction to a currently active area in the cross-section between theoretical computer science and physics. In last ten years it has been suggested that crit ...
参考文章(51)
Bart Selman, David Mitchell, Hector Levesque, Hard and easy distributions of SAT problems national conference on artificial intelligence. pp. 459- 465 ,(1992)
Jordan Erenrich, Bart Selman, Wei Wei, Towards efficient sampling: exploiting random walk strategies national conference on artificial intelligence. pp. 670- 676 ,(2004)
Marc Mézard, Riccardo Zecchina, Random K -satisfiability problem: From an analytic solution to an efficient algorithm Physical Review E. ,vol. 66, pp. 056126- ,(2002) , 10.1103/PHYSREVE.66.056126
Toby Walsh, Ian P. Gent, Towards an understanding of hill-climbing procedures for SAT national conference on artificial intelligence. pp. 28- 33 ,(1993)
Lenka Zdeborová, Marc Mézard, Hard constraint satisfaction problems ,(2008)
Guilhem Semerjian, Rémi Monasson, A Study of Pure Random Walk on Random Satisfiability Problems with “Physical” Methods theory and applications of satisfiability testing. pp. 120- 134 ,(2003) , 10.1007/978-3-540-24605-3_10
G. Biroli, R. Monasson, M. Weigt, A variational description of the ground state structure in random satisfiability problems European Physical Journal B. ,vol. 14, pp. 551- 568 ,(2000) , 10.1007/S100510051065
Marc Mézard, Giorgio Parisi, Riccardo Zecchina, Analytic and Algorithmic Solution of Random Satisfiability Problems Science. ,vol. 297, pp. 812- 815 ,(2002) , 10.1126/SCIENCE.1073287
Larry D. Auton, James M. Crawford, Experimental results on the crossover point in satisfiability problems national conference on artificial intelligence. pp. 21- 27 ,(1993)
Ken A. Dill, Sarina Bromberg, Dirk Stigter, Molecular driving forces : statistical thermodynamics in chemistry and biology Garland Science. ,(2003)