简单一维随机游动的若干性质及应用

摘要：

该文研究了一类简单的１维随机游动并证明了若干性质。文中应用这一模型分析了一类关于ｋ－ＳＡＴ问题的一致随机算法。对于２－ＳＡＴ问题，得出其时间复杂度下界为ｎ〈’２〉。此外对于一般的ｋ－ＳＡＴ问题，该文也作了相应的讨论。

关键词： 随机游动 k-SAT问题 随机算法

作者: 张立宇 张丕兴 朱洪

作者单位: 大学计算机科学系

会议类型: 国内会议

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

会议地点: 浙江金华

会议语种:中文

页码: 21～24

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