带随机步的可满足性算法

摘要	第1-6页
ABSTRACT	第6-8页
第一章 绪论	第8-12页
·SAT问题的研究背景	第8-9页
·研究动机	第9-10页
·研究的问题	第10页
·本文的主要工作及内容安排	第10-12页
第二章 SAT问题及相关知识	第12-17页
·引言	第12页
·SAT问题的基本符号和定义	第12-13页
·难解性问题	第13-14页
·P与NP	第14-15页
·Cook定理	第15页
·求解SAT问题的算法	第15-17页
第三章 随机算法	第17-25页
·引言	第17页
·随机算法及相关概念	第17-18页
·随机算法的分类	第18-19页
·随机算法的复杂度类	第19-20页
·随机算法的相关概率及求解框架	第20-24页
·相关概率	第20-21页
·随机算法的求解框架	第21-24页
·对随机算法研究的意义	第24-25页
第四章 膨胀图及相关概率	第25-36页
·引言	第25页
·膨胀图的基本知识	第25-31页
·膨胀图上的随机步概率上界估计	第31-36页
第五章 带随机步的可满足性算法	第36-42页
·引言	第36页
·膨胀图上随机步在算法设计中的应用	第36-37页
·利用膨胀图求解SAT问题的随机算法	第37-39页
·对本算法进行分析	第39-40页
·结论和进一步的工作	第40-42页
致谢	第42-43页
参考文献	第43-47页
附录	第47-48页