Upper bounds on the satisfiability threshold

被引：15

作者：

Dubois, O ^{[1
]}

机构：

[1] Univ Paris 06, CNRS, LIP6, F-75252 Paris 05, France

来源：

THEORETICAL COMPUTER SCIENCE | 2001年 / 265卷 / 1-2期

关键词：

satisfiability; SAT threshold; phase transition; upper bounds;

D O I：

10.1016/S0304-3975(01)00161-X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a survey of upper bounds which has been established up to now on the satisfiability threshold of random k-SAT formulae. The ideas which led to these bounds and the techniques used to obtain them, are explained. A companion paper in this volume present a survey of the lower bounds. (C) 2001 Elsevier Science BY. All rights reserved.

引用

页码：187 / 197

页数：11

共 37 条

[1] Lower bounds for random 3-SAT via differential equations [J].