计算机科学与技术系博士学位论文答辩
计算机科学与技术系计算机科学与技术系博士学位论文答辩博士学位论文答辩
计算机科学与技术系计算机科学与技术系博士学位论文答辩博士学位论文答辩
可满足性问题的算法设计与分析可满足性问题的算法设计与分析
可满足性问题的算法设计与分析可满足性问题的算法设计与分析
研研 究究 生：贺思敏生：贺思敏
研研 究究 生：贺思敏生：贺思敏
指导教师：张指导教师：张 钹钹 教授教授
指导教师：张指导教师：张 钹钹 教授教授
1997.5.28
- 1 -
1. 选题背景选题背景
选题背景选题背景
• 一个问题：清华大学排课表问题
科学研究要健康发展，科学研究要健康发展，应当面向真应当面向真
科学研究要健康发科学研究要健康发展，展，应当面向真应当面向真
实问题的求解。实问题的求解。
实问题的求解。实问题的求解。
排课表问题 → SAT 问题
• 一个方法：局部搜索
2. 透视计算复杂性理论透视计算复杂性理论
透视计算复杂性理论透视计算复杂性理论
SAT: 70 年代 最优解
第一个 NP 完全问题
90 年代 近似解
Max-3-SAT: 1.258 可近似
1.038 不可近似(P≠NP)
启发式算法：有限合理性
- 2 -
• 成果特点：计算机不能做什么
• 技巧特点：不直接构造算法
P≠NP
P =? NP
P=NP
NP 完全问题在科学研究和实际应完全问题在科学研究和实际应
完全问题在科学研究和实际应完全问题在科学研究和实际应
用中广泛存在，用中广泛存在，仅仅指出它们的难解性是仅仅指出它们的难解性是
用中广泛存在，用中广泛存在，仅仅指出它们的难解性是仅仅指出它们的难解性是
不够的，更重要的是正面寻求解决方法，不够的，更重要的是正面寻求解决方法，
不够的，更重要的是正面寻求解决方法，不够的，更重要的是正面寻求解决方法，
其中的关键是算法的设计与分析。其中的关键是算法的设计与分析。
其中的关键是算法的设计与分析。其中的关键是算法的设计与分析。
• 计算复杂性理论的局限性
以不变(算法)应万变(问题)，
最坏情况
算法设计应当面向每一个实例的求算法设计应当面向每一个实例的求
算法设计应当面向每一个实例的求算法设计应当面向每一个实例的求
解，以万变应不变、以万变应万变。解，以万变应不变、以万变应万变。
解，以万变应不变、以万变应万变。解，以万变应不变、以万变应万变。
- 3 -
例 1. 《科学美国人》94 年 7 月
“一个129 位数的密码提前 4 亿亿年被破译”
例 2. 《个人电脑》96 年 9 月
“Netscape 安全防线崩溃”
1995.7.14 RC4 算法 40 位密码加密后的信息
1995.8.15 法国博士生，8 天，盲目猜测，
