摘要：一般说来，寻找满足一定结构性质的对象结构是困难的。概率方法提供了解决此类问题的途径：证明满足一定结构性质的对象的概率大于零。在概率方法中，局部引理是一个关键技术。本文介绍了局部引理的基本原理和使用方法，并将其应用到估计（r，s）-SAT问题中临界函数的下界。

关键词：概率方法 临界函数 

单位：贵州大学计算机科学系 贵州贵阳550025 广西师范学院数学与计算机科学系 广西南宁530001