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

摘要：

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

关键词： 概率方法 局部引理 临界函数 对象结构

作者: 邓天炎 张庆顺 许道云

作者单位: 贵州大学计算机科学系,贵州,贵阳,550025;广西师范学院数学与计算机科学系,广西,南宁,530001 贵州大学计算机科学系,贵州,贵阳,550025

会议类型: 国内会议

会议名称: 2008年全国理论计算机科学学术年会

会议地点: 西安

会议语种:中文

页码: 68-71

在线出版日期: 2008-09-19（万方平台首次上网日期，不代表论文的发表时间）