算法分析与设计2005春.课件.第14讲.pdf

内容提要
•计算模型与计算复杂度关系
NP完全性理论介绍•问题分类:【P】与【NP】类
•NP-难【hard】问题,NP完全集
清华大学•第一个NPC问题和NPC问题集
宋斌恒•如何证明一个问题是NPC问题
清华大学宋斌恒 1 清华大学宋斌恒 2
引言 NPC问题
•脑力劳动机械化【吴文俊先生】•P-NP-NPC问题定义及其猜想:NPC是
•图灵机的停机问题:是否存在一个图灵机,他一类不可以在多项式时间内计算的问
可以回答其它图灵机是否停机【既算法是有界题。
的】
•如果在量子计算模型中上述问题又如
•原则上是否存在一般数学问题的解题步骤的判何?
决问题【希尔波特第十问题变种】
•图灵公理:凡是可计算的函数都可以用一台图
灵机来计算
清华大学宋斌恒 3 清华大学宋斌恒 4
明代数学家程大位著《算法统
下面介绍计算机械化的进程宗》中关于珠算的插图
清华大学宋斌恒 5 清华大学宋斌恒 6
1
机械式手动计算机机械计算机
•法国数学家、哲学家帕斯卡在1642年发
明了一种机械计算机,并与1649年取得
专利。帕斯卡的计算机采用一种齿轮系
统,其中一小轮转十个数字,下一个小
轮便转动一个数字,通过齿轮系的联
动,可以进行加法和减法的运算.
清华大学宋斌恒 7 清华大学宋斌恒 8
图灵图灵机模型
•大半个世纪以来,数学家、计算机
科学家提出了各种各样的计算模型
都被证明是同图灵机器等价的。这
一理论已被当成公理,它不仅是计
算机科学的基础,也是数学的基础
之一。为纪念英国数学家Turing
(1912-1954) 而设立的图灵奖成为计
算机界的诺贝尔奖.
清华大学宋斌恒 9 清华大学宋斌恒 10
图灵机模型图灵机定义
•图灵机模型用一个无限长的带子作为无限存储, •一个图灵机是一个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
清华大学宋斌恒 11 清华大学宋斌恒 12
2
多带图灵机, 非确定性的图灵机
•和普通图•在计算的任何时刻,机器可以在多种可能
灵机相似, 性中选择一种继续进行【永远选择正确
只是有多的,可以理解为全部分支都计算完后选
个带子,每出正确的】.它的计算是一课树,不同的分

有自己的算分枝导致接受状态,则接