| 摘要 | 第1-9页 |
| ABSTRACT | 第9-10页 |
| 第一章 引言 | 第10-13页 |
| ·研究背景及意义 | 第10-11页 |
| ·本文的主要工作和创新点 | 第11-12页 |
| ·本文的结构安排 | 第12-13页 |
| 第二章 P vs. NP 问题研究状态以及 MSP 问题 | 第13-20页 |
| ·P vs. NP 问题研究状态 | 第13-16页 |
| ·MSP 问题 | 第16-19页 |
| ·多级图 | 第16-17页 |
| ·简单路径 | 第17页 |
| ·MSP 问题 | 第17-18页 |
| ·对 MSP 问题的理解 | 第18-19页 |
| ·本章小结 | 第19-20页 |
| 第三章 可满足性问题求解算法研究 | 第20-33页 |
| ·可满足性问题研究进展 | 第20-22页 |
| ·可满足性问题到 MSP 问题的多项式归结 | 第22-29页 |
| ·问题描述 | 第22页 |
| ·归结思想 | 第22-23页 |
| ·归结算法 | 第23-24页 |
| ·归结的复杂性分析 | 第24-25页 |
| ·归结正确性证明 | 第25-29页 |
| ·用 Z-H 算法求解 SAT 问题的实验与验证 | 第29-32页 |
| ·测试方案一 | 第30-31页 |
| ·测试方案二 | 第31-32页 |
| ·测试结果 | 第32页 |
| ·小结 | 第32-33页 |
| 第四章 团问题求解算法研究 | 第33-39页 |
| ·最大团问题研究现状 | 第33-35页 |
| ·团问题到 MSP 问题的多项式归结 | 第35-38页 |
| ·问题描述 | 第35页 |
| ·归结思路 | 第35页 |
| ·归结算法 | 第35-36页 |
| ·归结的复杂度分析 | 第36页 |
| ·归结的正确性证明 | 第36-38页 |
| ·小结 | 第38-39页 |
| 第五章 三维匹配问题算法研究 | 第39-44页 |
| ·三维匹配问题研究现状 | 第39-40页 |
| ·三维匹配问题到 MSP 问题的多项式归结 | 第40-42页 |
| ·问题描述 | 第40页 |
| ·归结思想 | 第40页 |
| ·归结步骤 | 第40-41页 |
| ·归结的复杂性分析 | 第41-42页 |
| ·归结的正确性证明 | 第42页 |
| ·本章小结 | 第42-44页 |
| 第六章 结论与展望 | 第44-46页 |
| ·工作总结 | 第44页 |
| ·设想与展望 | 第44-46页 |
| 致谢 | 第46-47页 |
| 参考文献 | 第47-51页 |
| 作者在学期间取得的学术成果 | 第51-52页 |
| 在读硕士期间参加的科研项目情况 | 第52页 |