Lecture 10. NP完全性理论
清华大学 软件学院
清华大学 1
内容提要
? 计算模型与计算复杂度关系 ? 问题分类：【P】与【NP】类 ? NP－难【hard】问题，NP完全集 ? 第一个NPC问题和NPC问题集 ? 如何证明一个问题是NPC问题
清华大学 2
涉及到的算法理论基础
? 原则上是否存在一般数学问题的解题步骤的判决问题【希尔波特第十问题】
? 图灵机的停机问题：是否存在一个图灵机，他可以回答其它图灵机是否停机【既算法是有界的】
? 图灵公理：凡是可计算的函数都可以用一台图灵机来计算
? P－NP－NPC问题定义及其猜想：NPC是一类 不可以在多项式时间内计算的问题。
清华大学
3
明代数学家程大位著《算法统 宗》中关于珠算的插图
清华大学 4
机械式手动计算机
清华大学 5
机械计算机
? 法国数学家、哲学家帕斯卡在1642年发明了一种机械计算机，并与1649年取得专利。帕斯卡的计算机采用一种齿轮系统，其中一小轮转十个数字，下一个小轮便转动一个数字，通过齿轮系的联 动，可以进行加法和减法的运算.
清华大学 6
图灵
? 大半个世纪以来，数学家、计算机科学家提出了各种各样的计算模型都被证明是同图灵机器等价的。这一理论已被当成公理，它不仅是计算机科学的基础，也是数学的基础之一。为纪念英国数学家Turing (1912-1954) 而设立的图灵奖成为计算机界的诺贝尔奖.
清华大学 7
图灵机模型
清华大学 8
图灵机模型
? 图灵机模型用一个无限长的带子作为无限存储 , 它还有一个读写头 ,这个读写头能在带子上读 , 写和移动 : 开始时 ,带子上只有输入串 ,其它地方都是空的.当它需要保存信息时 ,读写头就把信息写在带子上 .为了读某个输入或写下的信息,带子可能将读写头往回移动到这个信息所 在的地方 .这样读 ,写和移动 ,机器不停的计算 , 直到产生输出为止 .机器实现设置了两种状态 : 接受或 拒绝
清华大学
9
图灵机定义
? 一个图灵机是一个7元组(Q,∑,Γ,δ,q0,q1,q2), 其中Q,∑,Γ都是有穷集合,并且 ? 1) Q 是状态集. ? 2) ∑是输入字母表,不包括特殊空白符号︺. ? 3) Γ 是带字母表,其中: ︺∈Γ,∑是Γ的子 集.
? 4) δ: Q×Γ→Q×Γ×{L,R}是转移函数. ? 5) q0∈Q是起始状态. ? 6) q1∈Q是接受状态. ? 7) q2∈Q是拒绝状态,且 q2≠q1
清华大学
10
清华大学算法分析与设计课件第10讲_NP完全性理论
