算法设计与分析 第2版 第11章-计算复杂性理论.ppt

　　从中看出，对于一个输入串而言，可能存在着若干个演变过程，其中任何一个演变过程最后导致一个终止状态，则这个输入串就被非确定性图灵机接受。 　　同样，也可以定义多带非确定性图灵机。 　　对于任意一个非确定性图灵机M，存在一个确定性图灵机M，使得它们的语言相等，即L(M)=L(M)。 3. 图灵机的停机问题与可计算性度量 　　一个图灵机并不是对任何输入都能停机。一般来说，一个图灵机M对一个输入串w的工作过程可能遇到三种情况： 　　（1）进入终止状态，这时M停机，并接受w。 　　（2）未进入终止状态，但δ无定义，此时M停机，但不接受w。 　　（3）一直不进入终止状态，且δ一直有定义。这时进入死循环，M永不停机。 　　可计算函数与可计算语言的定义与图灵机的停机问题有密切的关系。 　　若一个语言被一个图灵机M接受，且对任意输入串w，M都停机，称之为递归语言。一个语言是可计算的，当且仅当它是一个递归语言。同样，一个函数是可计算的，当且仅当它是完全递归函数，即存在图灵机M实现其计算功能，对于任意输入，M都能停机。 　　从根本上说，一个算法就是一个确定的、对任意输入都停机的图灵机。 　　确定性图灵机是现代电子计算机的理论模型。 一个对任意输入都停机的确定图灵机在多项式时间内可解的问题，必然存在多项式时间复杂度的计算机求解算法。 　　一个算法实质上就是一个以任何输入都停机的图灵机，因此已经找到的多项式时间界的计算机算法的问题都属于P类问题。 　　非确定性图灵机只是一种理论上的计算模型。不确定图灵机可解的问题，虽然也可以用确定性图灵机求解，但时间上的耗费（或说求解步数）是不一样的。 　　用非确定性图灵机以多项式时间界可求解的问题，用确定性图灵机不能保证在多项式时间界内可求解，但用确定性图灵机以指数时间界是肯定可以求解的。 　　用确定性图灵机以多项式时间界可解的问题称为P类问题，P指确定性图灵机上的具有多项式算法的问题集合。 　　用非确定性图灵机以多项式时间界可解的问题称为NP类问题，NP指非确定性图灵机上具有多项式算法的问题集合，这里N是不确定的意思。 　　“P=NP？”这个问题，作为理论计算机科学的核心问题，其声名早已经超越了这个领域。 它是Clay研究所的七个百万美元大奖问题之一，在2006年国际数学家大会上，它是某个1小时讲座的主题。　 　　NP问题的代表问题之一是旅行商旅行（TSP）问题。 　　目前发现的NP问题还有很多，如布尔表达式的可满足性问题、图的顶点覆盖问题和背包问题等等。 NPC（NP-completeness）的概念表明找到某个问题的有效算法至少和找NP中所有问题的有效算法一样难。 这里的有效性的含义是指为求解问题设计的算法的时间为多项式级的。 设L1?　　，L2?　　为两个语言，若存在映射f：　→　　，使得： 　　（1）存在多项式时间界的确定图灵机求解f： 　　（2）?x∈　　，x∈L1?f(x)∈L2 则称L1可以多项式规约为L2，记为L1∝L2。例如，有向哈密尔顿回路问题可多项式规约为旅行商问题。 容易证明，多项式规约具有性质： （1）Q1∈P，若Q2∝Q1，则Q2∝P。 （2）若Q1∝Q2且Q2∝Q3，则Q1∝Q3。 　　设Q1为一个问题，若对任意问题Q∈NP都有Q∝Q1，则称问题Q1为NP困难的。NP困难问题可以说是比任一个NP问题都不会“更容易”求解的问题。 　　设Q1∈NP，若?Q∈NP都有Q∝Q1，则称Q1为一个NPC问题（NP完全问题）。显然NPC问题是NP问题的一个子集。 关于P类问题、NP类问题和NPC问题的关系如下： 　　1971年，S.A.Cook证明布尔表达式的可满足性问题是一个NPC问题，从而肯定地回答了NPC问题的存在性。随后人们通过多项式约归找出了许多NPC问题，并证明了任一NP问题都可以多项式归约为布尔表达式的可满足性问题。 　　归纳起来，NP问题包含P问题和NPC问题，目前属于多项式时间界求解的问题都属P问题，NPC问题是属于NP问题中最难的问题，目前尚不能确定能否用多项式时间界算法来求解。 　　但已证明，如果NPC问题中有一个问题能用多项式时间界算法求解，则所有NPC问题都可用多项式时间界算法求解。 第11章 计算复杂性理论简介 　　将存在多项式时间算法的问题看作是易解问题，将需要指数时间级算法解决的问题看作是难解问题。 11.1.1 求解问题的分类 　　归纳起来，在各种求解问题中，按求解问题算法的时间复杂度可分为3大类： 存在多项式算法的问题 肯定不存在多项式算法的问题 尚未找到多项式算法，也不能证明其不存在多项式算法的问题。第三类问题介于第一类和第二类之间。 　　当图灵机的读写头扫描到一个格的字符时，根据控制器的当前状态和扫描到的字