会议专题

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

该文研究了一类简单的1维随机游动并证明了若干性质。文中应用这一模型分析了一类关于k-SAT问题的一致随机算法。对于2-SAT问题,得出其时间复杂度下界为n〈’2〉。此外对于一般的k-SAT问题,该文也作了相应的讨论。

随机游动 k-SAT问题 随机算法

张立宇 张丕兴 朱洪

大学计算机科学系

国内会议

1999年全国理论计算机科学学术年会

浙江金华

中文

21~24

1999-10-01(万方平台首次上网日期,不代表论文的发表时间)