d-正则(k,s)-SAT问题的临界现象与结构性质

目录

第一章 引 言

1.1 研究背景和研究意义

1.2 国内外研究现状

1.3 本文主要研究内容

1.4 论文的组织结构

第二章 基础知识

2.1 基本的符号约定

2.2 CNF 公式的解与(a,b)-超解

2.3 CNF公式类

2.4 可满足性问题及多项式时间归约

2.5 临界现象

2.6 本章小结

第三章 d-正则(k, s)-SAT问题的临界现象

3.1 从k-CNF公式到d-正则(k, s)-CNF公式的归约方法

3.2 d-正则(k, s)-SAT问题的临界现象

3.3 临界函数f(k, d)的上下界

3.4 本章小结

第四章 唯一可满足的d-正则(k, s)-SAT问题

4.1 唯一可满足的d-正则(k, s)-CNF公式的构造方法

4.2 唯一可满足的d-正则(k, s)-CNF公式的存在条件

4.3 一个多项式时间的简约归约

4.4 本章小结

第五章 (1,0)-SAT问题的临界现象

5.1 (1,0)-超解的存在性

5.2 几类(1,0)-SAT问题的NP完全性

5.2.1 (1,0)-(k, s)-SAT问题的NP完全性

5.2.2 (1,0)-正则(k, s)-SAT问题的NP完全性

5.2.3 (1,0)-d-正则(k, s)SAT问题的NP完全性

5.3 (1,0)-SAT问题的临界现象

5.3.1 (1,0)-(k, s)-SAT问题的临界现象

5.3.2 (1,0)-正则(k, s)-SAT问题的临界现象

5.3.3 (1,0)-d-正则(k, s)-SAT问题的临界现象

5.4 本章小结

第六章 总结与展望

6.1 论文的主要贡献

6.2 研究展望

致谢

参考文献

附录：攻读博士期间的科研成果

声 明