Lower bounds for random 3-SAT via differential equations

被引:85
作者
Achlioptas, D [1 ]
机构
[1] Microsoft Corp, Microsoft Res, Redmond, WA 98052 USA
关键词
random; 3-sat; algorithms; differential equations;
D O I
10.1016/S0304-3975(01)00159-1
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
It is widely believed that the probability of satisfiability for random k-SAT formulae exhibits a sharp threshold as a function of their clauses-to-variables ratio. For the most studied case, k = 3, there have been a number of results during the last decade providing upper and lower bounds for the threshold's potential location. All lower bounds in this vein have been algorithmic, i.e., in each case a particular algorithm was shown to satisfy random instances of 3-SAT with probability 1 - o(1) if the clauses-to-variables ratio is below a certain value. We show how differential equations can serve as a generic tool for analyzing such algorithms by rederiving most of the known lower bounds for random 3-SAT in a simple, uniform manner. (C) 2001 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:159 / 185
页数:27
相关论文
共 31 条
[1]  
ACHLIOPTAS, 1999, RALCOM 97 SANT, P1
[2]   The analysis of a list-coloring algorithm on a random graph [J].
Achlioptas, D ;
Molloy, M .
38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1997, :204-212
[3]   Optimal myopic algorithms for random 3-SAT [J].
Achlioptas, D ;
Sorkin, GB .
41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2000, :590-600
[4]  
ACHLIOPTAS D, IN PRESS RANDOM CONS
[5]  
ACHLIOPTAS D, 2000, RANDOM 00 GEN P INF, V8, P85
[6]  
ACHLIOPTAS D, 2000, 32 ANN ACM S THEOR C, P28
[7]   ASYMPTOTIC NUMBER OF LABELED GRAPHS WITH GIVEN DEGREE SEQUENCES [J].
BENDER, EA ;
CANFIELD, ER .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1978, 24 (03) :296-307
[8]   A variational description of the ground state structure in random satisfiability problems [J].
Biroli, G ;
Monasson, R ;
Weigt, M .
EUROPEAN PHYSICAL JOURNAL B, 2000, 14 (03) :551-568
[9]  
BOLLOBAS B, 1999, SCALING WINDOW 2 SAT
[10]  
Bollobas B, 1980, EUR J COMBINAT, V1, P311