Results related to threshold phenomena research in satisfiability: lower bounds

被引：28

作者：

Franco, J ^{[1
]}

机构：

[1] Univ Cincinnati, ECECS, Cincinnati, OH 45221 USA

来源：

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

关键词：

satisfiability; phase transition;

D O I：

10.1016/S0304-3975(01)00158-X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 [计算机软件与理论];

摘要：

We present a history of results related to the threshold phenomena which arise in the study of random conjunctive normal form (CNF) formulas. In a companion paper (D. Achlioptas, Theoret. Comput. Sci., this volume) the major ideas used to achieve many of the lower bounds results on the location of the threshold are described in an informal, intuitive manner. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：147 / 157

页数：11

共 29 条

[1]

Optimal myopic algorithms for random 3-SAT [J].