随机正则公式的可满足性问题研究

第一章 引 言

1.1 研究背景与现状

1.2 本文主要研究内容

1.3 论文的组织结构

第二章 基础知识

2.1 可满足性问题

2.2 因子图

2.3 随机正则公式的可满足性问题

2.4 随机k-SAT问题和随机正则(k, r)-SAT问题的相变现象

2.5 矩方法

2.6 本章小结

第三章 随机正则(k, r)-CNF公式的实例生成模型

3.1 k-SAT问题实例生成模型

3.2 格局模型

3.3 GRR(N, k, r)模型

3.4 随机正则(3, r)-SAT问题的难解实例产生模型

3.5 本章小结

第四章 基于渐近系数的随机正则公式的可满足临界

4.1 生成函数展开项系数的近似

4.2 随机正则(3, r)-SAT问题的可满足临界

4.3 基于渐近系数的随机正则公式的可满足临界

4.4 数值结果

4.5 本章小结

第五章 基于概率方法的随机正则公式的可满足临界

5.1 局部极限准则

5.2 基于概率方法的随机正则公式的可满足临界

5.3 数值结果

5.4 本章小结

第六章 基于1RSB方法的随机正则公式的可满足临界

6.1 基于腔域方法的随机k-SAT问题的可满足临界

6.2 随机k-SAT问题解空间的几何结构

6.3 基于1RSB方法的随机正则公式的可满足临界

6.4 本章小结

第七章 结束语

7.1 论文的主要工作总结

7.2 研究展望

参考文献

附录一 攻读博士期间的科研情况

致谢

声明