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

• 作者: 张庆顺 许道云 邓天炎
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 概率方法 局部引理 (k,s)-SAT问题 临界函数
• 年，卷（期）: 2008,（11）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 68-71
• 页数: 4页
• 分类号: TP301.6
• 字数: 4346字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2008.11.021

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学系	125	460	12.0	16.0
2	张庆顺	贵州大学计算机科学系	3	8	1.0	2.0
3	邓天炎	贵州大学计算机科学系	14	26	3.0	4.0