第9章NP完全性理论

9.1.1 随机存取机RAM

布尔表达式的可满足性问题

合取范式的可满足性问题

三元合取范式的可满足性问题团问题哈密顿回路问题顶点覆盖问题旅行商问题

子集和问题

部分NP完全问题树

清华大学算法分析与设计课件第10讲_NP完全性理论

Lecture 10. NP完全性理论 清华大学软件学院 清华大学 1 内容提要 ?计算模型与计算复杂度关系 ?问题分类：【P】与【NP】类 ?NP－难【hard】问题，NP完全集 ?第一个NPC问题和NPC问题集 ?如何证明一个问题是NPC问题

涉及到的算法理论基础 ?原则上是否存在一般数学问题的解题步骤的判决问题【希尔波特第十问题】 ?图灵机的停机问题：是否存在一个图灵机，他可以回答其它图灵机是否停机【既算法是有界的】 ?图灵公理：凡是可计算的函数都可以用一台图灵机来计算 ?P－NP－NPC问题定义及其猜想：NPC是一类不可以在多项式时间内计算的问题。 清华大学 3 明代数学家程大位著《算法统宗》中关于珠算的插图

机械式手动计算机 清华大学 5 机械计算机 ?法国数学家、哲学家帕斯卡在1642年发明了一种机械计算机，并与1649年取得专利。帕斯卡的计算机采用一种齿轮系统，其中一小轮转十个数字，下一个小轮便转动一个数字，通过齿轮系的联动，可以进行加法和减法的运算.

图灵 ?大半个世纪以来，数学家、计算机 科学家提出了各种各样的计算模型 都被证明是同图灵机器等价的。这 一理论已被当成公理，它不仅是计 算机科学的基础，也是数学的基础 之一。为纪念英国数学家Turing (1912-1954) 而设立的图灵奖成为计 算机界的诺贝尔奖. 清华大学7 图灵机模型

图灵机定义 ?一个图灵机是一个7元组(Q,∑,Γ,δ,q0,q1,q2), 其中Q,∑,Γ都是有穷集合,并且 ?1) ?2) ?3) 集. ?4) ?5) ?6) ?7) Q 是状态集. ∑是输入字母表,不包括特殊空白符号︺. Γ是带字母表,其中: ︺∈Γ,∑是Γ的子δ: Q×Γ→Q×Γ×{L,R}是转移函数. q0∈Q是起始状态. q1∈Q是接受状态. q2∈Q是拒绝状态,且q2≠q1 图灵机模型 ?图灵机模型用一个无限长的带子作为无限存储, 它还有一个读写头,这个读写头能在带子上读, 写和移动: 开始时,带子上只有输入串,其它地方都是空的.当它需要保存信息时,读写头就把信息写在带子上.为了读某个输入或写下的信息,带子可能将读写头往回移动到这个信息所 在的地方.这样读,写和移动,机器不停的计算, 直到产生输出为止.机器实现设置了两种状态: 接受或拒绝 清华大学9

第1章 算法概论(4np完全性理论)

1 §1.3 NP 完全性理论

如何理解问题的难解？易解？多项式运行时间？ ?多项式的运行时间认为是易解算法，当然，你认为θ(n100)难解，但次数如此高的多项式时间问题非常少，且一般都会找到一个更有效的多项式时间算法。 ?对很多合理计算模型来说，在一个模型上用多项式时间可解的问题，在另一个模型上也可以用多项式时间获得解决。 2

如何理解问题的难解？易解？多项式运行时间？ 多项式时间可解问题类具有很好的封闭性。比如一个多项式时间算法输出给另一个多项式时间算法作为输入，或被另一个多项式时间算法作为子程序常数次调用，这样的组合算法运行时间也都是多项式的。 3

?一般来说，将可由多项式时间算法求解的问题看成易处理的问题，而把需要超多项式时间才能解决的问题看作难处理问题。 ?“NP完全”（NP-Complete）问题，它的状态是未知的，迄今为止，既没有人找出求解NP完全问题的多项式算法，也没人能够证明对这类问题不存在多项式时间算法。 ?P≠NP问题，自1971年提出以后，已经成为理论计算机科学研究领域中，最深奥和最错综复杂的开放问题之一了。 4

5 ? 从表面上看，有些NP 完全问题有着与多项式时间算法的问题非常相似的特点，这很诱惑。? 最短与最长简单路径：有向图G=(V,E)，单源最短路径可在O(|V|2)时间内完成，但寻找两个顶点间最长简单路径（无重复顶点）问题是NP 完全的。?欧拉游程和哈密顿回路：有向图G=(V,E)，欧拉游程指一个回路，遍历途中每条边一次，但可能不止一次的访问同一个顶点，这可在O(|E|)时间内找到。哈密顿回路也是一个回路，包含V 中每个顶点。确定有向图是否存在哈密顿回路的问题是NP 完全的。