| 摘要 | 第1-3页 |
| Abstract | 第3-5页 |
| 第一章 概论 | 第5-10页 |
| ·计算模型与复杂性 | 第5-6页 |
| ·NP 完全问题. | 第6-8页 |
| ·指数时间算法 | 第8-9页 |
| ·本文的主要结果 | 第9-10页 |
| 第二章 BT 算法模型 | 第10-19页 |
| ·BT 模型简介 | 第10-12页 |
| ·BT 模型的严格定义 | 第12-13页 |
| ·下界证明的一般思路 | 第13-14页 |
| ·背包问题的BT 下界 | 第14-19页 |
| 第三章 从k-SAT 到k-CSP | 第19-25页 |
| ·k-CSP 问题简介. | 第19-20页 |
| ·算法概述. | 第20-21页 |
| ·值域大小为常数 | 第21-22页 |
| ·值域大小可变 | 第22-23页 |
| ·α ≤1 | 第22-23页 |
| ·α > 1 | 第23页 |
| ·补遗 | 第23-25页 |
| 第四章 总结和待解决的问题 | 第25-27页 |
| 参考文献 | 第27-30页 |
| 已发表/待发表论文 | 第30-31页 |
| 致谢 | 第31-32页 |