局部引理及其在(r,s)-SAT问题中的应用

摘要

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