下载文档原格式
计算复杂性理论计算复杂性理论是计算机科学中重要的一个分支，它研究了计算问题的难度和可解性。
通过对问题的复杂性进行分析和分类，计算复杂性理论为我们提供了解决问题的指导原则和限制条件。
本文将介绍计算复杂性理论的基本概念、主要研究内容以及其在实际应用中的重要性。
一、基本概念1. P和NP问题在计算复杂性理论中，最基本的概念是P问题和NP问题。
P 问题是指可以在多项式时间内解决的问题，即存在一个算法可以在多项式时间内给出问题的正确答案。
而NP问题则是指可以在多项式时间内验证答案的问题，但尚未找到多项式时间内解决的算法。
P问题是NP问题的子集，即所有的P问题也是NP问题，但目前尚不清楚P问题和NP问题是否是相同的类。
2. NP完全性NP完全性是计算复杂性理论中的一个关键概念，它指的是一类最困难的NP问题。
一个问题被称为是NP完全的，如果它既是一个NP问题，又满足以下条件：对于任何一个NP问题，都可以用多项式时间的算法将其约化为该问题。
换句话说，如果我们能够找到一个多项式时间算法来解决一个NP完全问题，那么我们也可以用同样的算法来解决所有的NP问题。
3. NP难度除了NP完全性概念，计算复杂性理论还引入了NP难度的概念。
一个问题被称为是NP难度的，如果对于任何一个NP问题，都可以用多项式时间的算法将其约化为该问题。
虽然NP难度问题不一定是NP问题，但它们和NP完全问题一样，都是十分困难的问题。
二、主要研究内容1. 多项式时间算法计算复杂性理论的一个主要研究内容是寻找和分析多项式时间算法。
多项式时间算法是指可以在多项式时间内解决的算法，即其执行时间与输入规模呈多项式关系。
研究多项式时间算法的目标是寻找高效的解决方法，从而提高问题的可解性。
2. 算法复杂性分析算法复杂性分析是计算复杂性理论中的另一个重要内容。
通过对算法的复杂性进行全面的分析，我们可以预测算法在实际应用中的性能表现。
算法复杂性分析的主要方法包括时间复杂性分析和空间复杂性分析，通过对算法的时间和空间需求进行测量和评估，我们可以判断算法在给定条件下的可行性和效率。
浅谈计算复杂性理论任忠乌鲁木齐石化公司计控中心摘要：本文阐述了计算复杂性理论的产生、定义、研究内容和发展。
关键词：算法分析；计算复杂性；起源；发展1.计算法复杂性理论的起源在几千年的数学发展中，人们研究了各式各样的计算，创立了许多算法。
但是，以计算或算法本身的性质为研究对象的数学理论，却是在20世纪30年代才发展起来的。
1936年，为了讨论对于每个问题是否都有求解算法，数理逻辑学家提出了几种不同的计算模型的定义。
K.Godel和S.C.Kleene等人创立了递归函数论，将数论函数的算法、可计算性刻画为递归可枚举性。
A.M.Turing和E.L.Post提出了理想计算机的概念，将问题算法可解性刻画为在具有严格定义的理想计算机上的可解性。
40年代以后，随着计算机科学技术的发展，研究的焦点从理论可计算法转移到现实可计算性上。
人们不仅需要研究理论上的、原则上的可计算性，还要研究现实的可计算性，即研究计算一个问题类需要多少时间，多少存储空间，研究哪些问题是现实可计算的，哪些问题虽然原则上可计算，但由于计算的量太大而实际上无法计算等。
因而一般算法设计方法研究和对一类问题算法解的难度分析便成为计算机科学的热点。
此后，计算复杂性的研究等不断有所发展。
由此产生了算法学和计算复杂性理论等新兴研究领域。
计算复杂性大的进展始于50年代末、60年代初，当时在美国有两个并行的中心，一个是通用电气公司设立于纽约州Schenectady的研究实验室，核心人物是J.Hartmanis和R.Stearns。
1964年11月，他们在普林斯顿举行的第五届开关电路理论和逻辑设计学术年会上发表了论文"Computational Complexity of recursivese quences"，论文中首次使用了"计算复杂性"这一术语，由此开辟了计算机科学中的一个新领域，并为之奠定了理论基础。
他们两人是1993年度图灵奖获得者。
计算机科学中的计算复杂性理论计算复杂性理论是计算机科学中的一个重要分支，研究的是计算问题的算法复杂性和计算机问题的可解性。
它帮助我们理解计算问题是否有高效的解决方法，为设计和分析算法提供了基础。
一、引言计算复杂性理论涉及到算法的效率和计算问题的可解性，对计算机科学和信息技术具有重要意义。
本文将首先介绍计算复杂性理论的起源和发展，然后重点讨论几个计算复杂性理论中的重要概念和问题。
二、计算复杂性理论的起源和发展计算复杂性理论起源于20世纪60年代，由对计算问题的可解性进行研究逐渐演化而来。
该理论的研究者，如图灵奖得主阿隆佐·邱奇、史蒂芬·库克等，提出了多个理论模型和概念，奠定了计算复杂性理论的基础。
三、计算复杂性理论的重要概念1. P问题和NP问题在计算复杂性理论中，P问题指的是可以在多项式时间内解决的问题，而NP问题则是指可以在多项式时间内验证给定解是否正确的问题。
其中，P问题是NP问题的一个子集，即P⊆NP。
2. NP完全性NP完全性是计算复杂性理论中的一个重要概念。
一个问题是NP完全的，意味着它是NP问题中最难的一类。
如果我们能够找到一个多项式时间内解决NP完全问题的算法，那么可以得出P = NP的结论，这是计算机科学中的一个重大问题。
3. 计算复杂性度量计算复杂性理论通过引入时间复杂性和空间复杂性度量来衡量算法的效率。
其中，时间复杂性度量算法执行所需的时间步数，空间复杂性度量算法所需的存储空间。
这些度量帮助我们选择具有高效率的算法，提高计算问题的解决速度。
四、计算复杂性问题的研究方法计算复杂性理论研究问题的方法主要有两种：证明方法和求解方法。
证明方法通过证明某个问题是NP完全的来研究问题难度；而求解方法则是通过设计高效的算法来解决问题。
1. 证明方法证明方法是计算复杂性理论中常用的方法之一，它使用约简技术将一个已知的NP完全问题转化为待研究问题，从而证明待研究问题也是NP完全的。
第二章算法问题及其复杂性2.1 什么是算法问题?1.算法问题(可解的问题)——简单地说，就是存在求解算法的问题。
例子（见书）2. 算法问题定义(1) 一个可行的（即语法正确的）输入集的描述——每个输入可表为在一个有限字母表上的有限字母串；(2)一个函数的描述——将每个输入映射到一个非空的正确输出集，每个输出也是一个有限字母表上的有限序列。
3. 问题和问题实例4. 关于算法问题的输入好算法的计算时间与问题的输入形式有关。
然而，一个问题的所有合理的输入形式往往导出的算法问题是类似的。
因此一般可以忽略问题的具体输入形式。
例如，一个图使用邻接表表示和用邻接矩阵表示看作是没有太大区别。
5. 算法问题的几种形式搜索问题、优化问题、求值问题、判定问题（形式语言）2.2 一些重要的算法问题1. 旅行商问题 (TSP)——有多种变型2. 0/1背包问题3. 划分问题4. 监控（覆盖）问题5. 团问题6. 组队问题7. 网络中的最优流问题8. 运动联盟的冠军问题9. 验证问题10. 数论问题（素数测试、分解质因数）2.3 如何度量算法的计算时间?1．什么是算法?——直观地讲，算法就是一个无歧义的指令集，它规定了根据输入如何一步步得出一个正确输出的步骤。
确定性算法——对于同一输入而言，算法每一时刻下一计算步骤都是唯一确定的。
随机算法——对同一输入而言，每一时刻算法下一计算步骤可能依一个随机数来定。
2．一个算法的计算时间如何度量?算法的计算时间依赖于诸多因素：输入、计算机、程序设计语言、算法的实现…但是有些因素的影响是有限的并且也是可控的。
算法的计算时间可以简化为仅仅依赖于算法本身和输入大小。
计算时间是用运算步骤而不是具体时间来度量。
3．计算模型寄存器机（Register Machine），即随机存取机(Random Access Machine).对数成本模型(Logarithmic Cost Model)——认为在数n上的算术运算的成本为O(log n)。
计算复杂性理论总结报告(总10页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--计算复杂性理论总结报告一、图灵机（1）图灵机基本模型图灵机是由图灵（Alan Mathisom Turing）在1936年提出的，它是一个通用的计算模型。
通过图灵机，来研究递归可枚举集和部分递归函数，对算法和可计算性进行研究提供了形式化描述工具。
图灵机的基本模型包括一个有穷控制器，一条含有无数个带方格的输入带和一个读写头。
其直观物理模型如下图1所示。
基本图灵动作有以下三种：（1）改写被扫描带方格内容，控制器转化为下一状态。
（2）读写头向左移一个带方格，控制器转化为下一状态。
（3）读写头向左移一个带方格，控制器转化为下一状态。
图1图灵机（2）图灵机形式化定义，图灵机演算过程及语言描述定义：一个基本图灵机定义为一个七元组 TM={Q,C,δ,A,B,q1,F}。
其中Q是状态集合，（图灵机所有的状态）非空有限集；C是带符号表，（放在带方格中的符号集合）非空集；δ是控制函数或过程转换函数（定义控制器）δ：QxC QxC∪（R,L）；A是输入字母表，A⊆C；B是空白符，B∈C；q1是初始状态，q1∈Q；F是终态集，F ⊆Q.TM的扫描符号串主要由δ来确定：（1）δ（q，s）=（q’,s’）;（2）δ（q，s）=(q’,R);（3）δ（q，s）=(q’,L);（4）δ（q，s）无效，对应无定义时图灵机终止。
TM的工作用“格局”的转换来描述。
格局：σ：a1a2a3…aj-1qajaj+1…其中q∈Q，ai∈C；（1）若δ（q，ai）无定义，称σ为停机格局；（2）若q∈F，称σ为接受格局；（3）若q为初始状态，称σ为初始格局；格局σ到格局τ的转换σ├mτ若成立σ=σ1├m1σ2├m2σ…3├Mσk 记为σ1├*σk （k>=0）（3）图灵机其他形式（1）五元机δ：QxC→QxCx{R,L}基本动作：qsq’s’即δ（q，s）=（q’,s’）；qsq’L即δ（q，s）=（q’,L）；qsq’R即δ（q，s）=（q’,R）。
计算复杂性理论计算复杂性理论是理论计算机科学的分支学科，使用数学方法对计算中所需的各种资源的耗费作定量的分析，并研究各类问题之间在计算复杂程度上的相互关系和基本性质，是算法分析的理论基础。
计算模型与计算资源计算复杂性理论的研究对象是算法在执行时所需的计算资源，而为了讨论这一点，我们必须假设算法是在某个计算模型上运行的。
常讨论的计算模型包括图灵机（Turing machine）和电路（circuit），它们分别是一致性（uniform）和非一致性（non-uniform）计算模型的代表。
而计算资源与计算模型是相关的，如对图灵机我们一般讨论的是时间、空间和随机源，而对电路我们一般讨论电路的大小。
由邱奇-图灵论题（Church-Turing thesis），所有的一致的计算模型与图灵机在多项式时间意义下是等价的。
而由于我们一般将多项式时间作为有效算法的标志，该论题使得我们可以仅仅关注图灵机而忽略其它的计算模型。
判定型问题和可计算性我们考虑对一个算法问题，什么样的回答是我们所需要的。
比如搜索问题：给定数组A，和一个数s，我们要问s在不在A中（判定性问题，decision problem）。
而进一步的，s如果在A中的话，s的位置是什么（搜索型问题，search problem）。
再比如完美匹配问题（perfect matching）：给定一个二分图G=(V,E)，我们问是不是存在边集E，使得二分图中每个结点恰好属于该边集的一条边（判定型问题）。
而进一步的，E存在的话，E具体是什么（搜索型问题）。
自然的，我们会发现对于一般的算法问题A，我们都可以这样来问：首先，解是不是存在的？其次，如果解存在，这个解具体是什么？这就是A的判定型问题和A的搜索型问题（又称函数型问题）区分来源的直观解释。
对判定型问题的回答只需是“是”或“否”，而对搜索型问题，需要返回解的具体形式或者“解不存在”。
所以一个对A 的搜索型问题的算法自然的也是对A的判定型问题的算法。
第三章计算复杂性理论主要内容3.1 Turing机3.2 计算复杂性理论3.3 NP完全性理论的基本概念3.4 NP完全性证明3.5 用NP完全性理论分析问题3.6 NP难度3.1 Turing机一、Turing机的定义1. 基本模型2. 基本Turing机的变种单向带的Turing机k条带的Turing机非确定型的Turing机二、Turing机模型的等价性1. 单向带Turing机与基本Turing机等价2. k条带的Turing机与基本Turing机等价3. 非确定型Turing机与基本Turing机等价一、Turing机的定义1. 基本模型双向无限带的Turing机M = <Q,∑,Γ,δ,q,B,F>, 其中Q 有穷状态集Γ有穷带字符集∑输入字符集∑⊂ΓB 空白字符, B∈Γ－∑q 0初始状态, q∈QF 终结状态集, F⊂Q,qY ,qN∈Fδ: (Q－F)×Γ→Q×Γ×{L,R} 状态转移函数(ID)α1qα2表示此刻Turing机的FSC处于状态q,读写头指在串α2的第一个字符.例如Turing机M的某时刻的状态转移函数是δ(q,xi) = (p,Y,L)带上的字符串为x1x2...xi...xn, 读写头指向字符xi, 则它的瞬间描述是:x 1x2...xi-1qxi...xn┣x1x2...x i-2px i-1Yx i+1...x n ┣表示由左边的ID一步达到右边的ID┣*表示由左边的ID经有限步达到右边的ID被M接受的语言记作L(M)，是∑*上的字的集合.当这些字左端对齐方格1放在带上,M处于状态q,M的带头指向方格1时, 经过有限步M将停机在接受状态qY, 即L(M)={ω|ω∈∑*,∃α1,α2∈Γ*(qω⊢*α1qYα2)}如果字ω不是L(M)中的字, M可以不停机或停机在拒斥状态qN.例1 L={0n1n|n≥1}, 设计接受L的Turing机如下: M = <Q,∑,Γ,δ,q,F>Q = {q0,q1,q2,q3,qY},∑= {0,1},Γ= {0,1,X,Y,B},F = {qY }. 其中qY代表接受停机状态.初始将字符串放在从1到n方格中, FSC处在状态q, 读写头指向方格1.将第一个0改写成X, 然后带头向右扫描. 遇到第一个1, 将1改为Y, 然后带头向左扫描. 遇到第一个X改为向右扫描. 这时进入下一个巡回.每个巡回将一对0和1改为X和Y, 直到接受或拒斥停机.例如输入0011,Turing 机动作如下：q 00011┣Xq 1011┣X0q 111┣Xq 20Y1┣q 2X0Y1┣Xq 00Y1 ┣XXq 1Y1┣XXYq 11┣XXq 2YY ┣Xq 2XYY ┣XXq 0YY ┣XXYq 3Y ┣XXYYq 3┣XXYYq Y转移函数如下（其中__代表拒斥停机状态）1X Y B q 0(q 1,X,R)____(q 3,Y,R)__q 1(q 1,0,R)(q 2,Y,L)__(q 1,Y,R)__q 2(q 2,0,L)__(q 0,X,R)(q 2,Y,L)__q 3______(q 3,Y,R)q Y2．基本Turing机的变种单向无限带的Turing机带方格从1开始, 向右无限长. 其它与基本Turing机相同.多带的Turing机k条双向带, k个读写头, 其中k为大于1的常数. 初始将输入写在第一条带的方格1到n内. 其它带为空. 每个读写头扫描一条带,可以改写被扫描方格的字符, 读写头然后向左或向右移动一个方格. 读写头的动作由FSC的状态及k条带所扫描的k个字符来决定.非确定型的Turing机(NDTM)一个有限状态控制器FSC, 猜想模块GM, 读写头, 只写头, 双向无限带.状态, 带方格的1到n写上输入x, 初始FSC处于q其它方格为空白字符B. 读写头指在方格1, 只写头指在方格-1.计算分为猜想阶段和检查阶段.猜想阶段状态下的待用状态.FSC处于q猜想模块GM指挥只写头,每次一步在所扫描的方格内写下 中的某个字符, 然后左移一个方格或不动.到某个时刻, 猜想模块进入待用状态, 这时有限状状态下的活跃状态. 从此刻起, 计算进态控制器进入q入检查阶段，而猜想模块是否继续动作, 或怎样动作, 完全是任意的.检查阶段与确定型的Turing机完全一样. 如果FSC进入接受状态, 则计算停止, 接受x. 如果进入拒斥状态, 则计算停止, 不接受x.二、Turng机的等价性定理1 语言L被一个具有双向无限带的Turing机M2接受当且仅当L被一个具有单向无限带的Turing机M1接受.定理2 语言L被一个k条无限带的Turing机M1接受当且仅当L被一个双向无限带的Turing机M2接受.定理3 语言L被一个非确定型的Turing机M1接受当且仅当L被一个确定型的Turing机M2接受.3.2 计算复杂性的基本概念一、空间和时间复杂性的形式定义1.确定型Turing机空间复杂性:离线的Turing机M,1条具有端记号的只读输入带,k条半无限存储带.如果对每个长为n的输入串, M在任一条存储带上都至多扫视S(n)个单元, 那么称M在最坏情况下的空间复杂度为S(n).时间复杂性:k条带的Turing机M, M有k条双向带, 一条带包含输入.如果对于每个长为n的输入串, M在停机前至多做T(n) 个动作, 那么称M在最坏情况下的时间复杂度为T(n).两条假设：空间复杂性至少需要1, 时间复杂性至少需要读入输入的时间, 因此这里作如下假定:对一切n,S(n)≥1,logn 是max{1,⎡logn⎤}的缩写.对一切n,T(n)≥n+1, T(n)是max{n+1,T(n)}的缩写.例1 L = {wcw R| w为0-1字符串},设计接受L的Turing机M1和M2, 使得M1的时间复杂度为O(n), M2的空间复杂度为O(log n).M1有2条带,把c左边的w复制到第2条带上. 当发现c时第2条带的读写头向左, 输入带的读写头向右. 比较两个带头的符号, 如果符号一样, 字符个数一样, M1接受x. M1至多作n+1个动作. 时间复杂度为n+1. 空间复杂度为⎡n-1/2⎤+1.M2有2条带, 第2条带作为二进制的计数器. 首先检查输入是否只有1个c, 以及c左边和右边的符号是否一样多. 然后逐个比较c左边和右边的字符, 用上述计数器找到对应的字符. 如果所有的字符都一样, M2接受停机. 空间复杂度为二进制的计数器的占用空间, 即O(log n). 时间复杂度为n2.2. 非确定型Turing机给定串x, M接受x的时间: M关于x的所有接受计算中, 在猜想阶段和检查阶段直到进入接受停机状态为止所发生步数的最小值.M的最坏情况下的时间复杂性T(n)=max{m|存在x∈L,|x|=n,M接受x的时间为m}给定串x, M接受x的空间: M关于x的所有接受计算中, 在猜想阶段和检查阶段直到进入接受停机状态为止在存储带上扫视的最少单元数.M的最坏情况下的空间复杂性S(n)=max{m|存在x∈L,|x|=n, M接受x的空间为m}二、带压缩、线性加速和带数目的减少带压缩：由于Turing机的状态数和带字符集的大小可以是任意给定的常数. 可以将若干个带字符编码成一个字符, 所以空间占用量总可以压缩一个常数因子.线性加速：使得计算加速一个常数因子.带数目的减少：在空间或时间复杂性不变的情况下减少带的数目.这里对Turing机进行一点修改, 允许带头原地不动.1. 带压缩（使用空间长度的线性减少）定理1 如果语言L 被一个具有k 条存储带S(n)空间有界的Turing 机(TM)接受, 则对任意1>c>0, L 被一个cS(n) 空间有界的TM 接受.2. 时间线性加速∞=∞→nn T Inf n )(那么，L 就可以被一个k 带cT(n)时间有界的TM M 2接受, 其中c 是大于0的任意常数.定理2 如果语言L 被一个k 带T(n)时间有界的TM M 1接受,那么只要k>1, 且定理3如果对于k>1和某个常数c>1, L被一个k带cn时间有界的TM接受, 则对于每个ε>0, L被一个k带(1+ε)n 时间有界的TM接受.推论1如果对于某个c>1,T(n)=cn, 则对任何ε>0,DTIME(T(n))= DTIME((1+ε)n)推论2如果对于某个c>1,T(n)=cn, 则对任何ε>0, NTIME(T(n)) = NTIME((1+ε)n)3. 带数目的减少（空间不增加下带数目的减少）定理4 如果语言L被一个具有k条存储带S(n)空间有界的TM接受, 那么L可以被一个具有1条存储带的S(n)空间有界的TM接受.4. 时间复杂性与带数目的减少定理5如果L在DTIME(T(n))中, 那么L可被一个单带TM在时间T2(n)内被接受.推论L在NTIME(T(n))中, 则L可以被一个非确定型T2(n)时间有界的TM接受.定理6如果L可以被一个k带T(n)时间有界的TM 接受, 则L可以被一个2带TM在T(n)logT(n) 时间内接受.推论如果L被一个k条带T(n)时间有界的NDTM接受, 则L也可以被一个双带T(n)logT(n) 时间有界的NDTM接受.小结：减少带数目，可以保证空间复杂性不变.减少带数目，时间复杂性增加.小结：1. 带压缩（空间的线性减少）M1: k 条存储带, S(n)空间存在M2: k 条存储带，cS(n)空间，1>c>02. 时间线性加速（时间的线性减少）（1）M1: k 带（k>1)，T(n)时间（）存在M2: k 带(k>1)，cT(n)时间，1>c>0（2）M1: k 带（k>1)，cn 时间,c>1存在M2: k 带（k>1),(1+ε)n 时间,任给ε>03. 带数目的减少（1）M1: k 带（k>1), S(n)空间，存在M2：单带, S(n)空间（2）M1: k 带（k>1), T(n)时间存在M2：单带, T 2(n)时间存在M2: 2带，T(n)logT(n)时间∞=∞→n n T Inf n )(3.3 NP完全理论的基本概念主要内容一、判定问题和语言判定问题定义与描述判定问题与语言的关系二、P类与NP类难解的问题与多项式可解的问题P类与NP类定义三、多项式变换与NP完全性多项式变换的定义及性质NP完全的定义四、Cook定理证明了第一个NP完全问题（SAT）一、判定问题和语言主要内容1. 判定问题的定义2. 陈述判定问题的标准格式3. 引入判定问题的理由4. 判定问题的形式描述——语言5. 算法的形式描述——Turing机1. 判定问题的定义一个判定问题π= (Dπ,Yπ), 其中Dπ为实例集, Yπ⊆Dπ为肯定实例的集合. 任给实例I∈Dπ, 问I∈Yπ?2. 陈述一个判定问题的标准格式对实例中参数的一般描述和一个肯定--否定问题.子图同构问题实例: 两个图G1=(V1,E1), G2=(V2,E2)问: G1是否包含与G2同构的子图?即是否存在子集V’⊆V1, E’⊆E1使得|V’|=|V2|,|E’|=|E2|,且有双射f: V2→V’满足以下条件?{u,v}∈E2⇔{f(u),f(v)}∈E’3. 引入判定问题的理由(1) 判定问题的形式化描述简单.(2) 许多优化问题的难度与判定问题的难度相关.例如巡回售货员问题是一个优化问题. 如果在实例中加上参数B, 问是否存在长度不超过B的旅行? 得到一个巡回售货员的判定问题. 可以如下给出解该判定问题的算法：I. 先解对应的优化问题得到最优解, 时间为f(n)II.计算最优解的成本函数(旅行长度), 然后和B比较. 如果大于B,则回答No；否则回答Yes. 所用时间为g(n)g(n)为多项式时间,因此解巡回售货员判定问题的时间由f(n)确定. 如果对于巡回售货员优化问题存在多项式时间的算法, 那么也存在解相应判定问题的多项式算法.4. 判定问题的形式描述--语言语言的定义设∑为有穷字符集, ∑*是∑上所用有穷字符串的集合. 称∑*的任何子集为∑上的语言.判定问题与语言的关系在合理的编码系统e下, 判定问题的任意实例被编码成一个字符串x.例如巡回售货员的判定问题的实例如下图相应的字符串是:∑= {c,[,],/,0,1,2,3,4,5,6,7,8,9,#}c[1]c[2]c[3]c[4]//10/5/9//6/9//3#25编码系统e将∑*中的字符串划分成三类:不是实例中的编码Dπ－Yπ中的实例的编码Yπ中的实例的编码只有Yπ中的实例的编码构成与判定问题π对应的语言L.具体定义如下:与判定问题π和编码系统e相关的语言L[π,e]设π为判定问题, e是关于π的编码系统, 其字符表为∑, 则L[π,e]={x∈∑*: x是某个实例I∈Yπ在e下的编码}I∈Yπ⇔x∈L[π,e]算法解判定问题π⇔用Turing机识别语言L[π,e]说明：对判定问题π, 相关的L[π,e]与编码系统有关.合理的编码系统:无冗余的符号和信息.数字用二进制(或其他进制，不允许用一进制）表示.可译码在不同的合理的编码系统下, 实例的编码所对应的输入长度length: Dπ→Z+多项式相关. 换句话说, e,e’为合理的编码系统, 实例I在e和e’下的编码所对应的输入长度分别为length[I] 和length’[I], 则存在多项式P和P’使得length’[I]≤P(length[I]), length[I]≤P’(length’[I])二、P类与NP类1. 难解的问题定义实例2. P类与NP类的定义非形式定义（问题类）形式定义（语言类）3. P类与NP类的关系P NPP=NP?1.难解的问题不存在确定型多项式时间算法的问题难解的原因问题太难, 在多项式时间不可能找到解解本身太庞大, 表示解的符号串长度不是输入长度的多项式函数一般只考虑第一种难解的问题两类难解的问题不可判定问题——不存在算法可判定的难解问题——有算法，但不存在多项式时间的算法停机问题是不可判定的定理1 不存在根据任意Turing机T的定义, 能够确定T在输入d上是否停机的算法.T证明思路：证明T在输入T上停机是不可判定的反证法：假设存在Turing机H，可以对任何Turing机T，判定T在T上是否停机.根据H，构造Turing机L,使得L在L上停机⇒L在L上不停机L在L上不停机⇒L在L上停机证假定H是一个可以判定T在T上是否停机的Turing机. H有两个停机状态:Yes停机状态⇔T在T上停机No 停机状态⇔T在T上不停机构造新的Turing机L. L比H多两个新的状态q1’, q2’.H进入Yes停机状态当且仅当L转移到q1’. 并且设定转移函数, 对一切u∈∑有δ(q1’,u) = (q2’,u,R)，δ(q2’,u) = (q1’,u,L)H进入No停机状态, L也进入No停机状态. 从而有T在T上停机⇔L在T上不停机T在T上不停机⇔L在T上停机令T=L, 则导致L在L停机⇔L在L上不停机L在L不停机⇔L在L上停机产生矛盾.可判定的难解问题实例:非确定型的难解问题(用非确定型的Turing机在多项式时间不可能解出)判定半扩展正则表达式是否表示它的字母表上的所有的串. The Design and Analysis of Computer Algorithms, Aho, Hopcroft, Ullman. 1972.NP类问题是判定问题用非确定型的算法在多项式时间可解到目前还没有找到多项式时间的确定型算法是否为难解的问题（不清楚）2. P类和NP类的定义(1) 非形式的定义P类: 用确定型算法在多项式时间可解的判定问题类NP类: 用非确定型算法在多项式时间可解的判定问题类非确定型算法求解判定问题π任意给定实例I∈Dπ, 如果I∈Yπ, 则存在结构s，使得当对输入I猜想s时，检查阶段回答Yes; 如果I∉Yπ, 则不存在结构s，使得当对输入I猜想s时，检查阶段回答Yes.多项式时间的非确定型算法对于解判定问题非确定型算法, 如果存在多项式P，对每个实例I∈Yπ存在猜想s，使得检查阶段在时间P(length[I])内回答Yes.几点说明：1. 猜想的结构s的规模小于P(length[I])2. 对肯定实例I∈Yπ，至少存在一个猜想s，使得检查阶段在时间P(length[I])内回答Yes,而不管其他猜想.3. 对否定实例I∈Dπ－Yπ的运算可以不管.4. 可以看成具有无限并行能力的计算机. 将所有可能的结构猜想出来, 每个结构一道, 如果有一个回答Yes, 则整个机器停机并回答Yes; 使得机器回答Yes的最短时间就是计算时间.5. 肯定与否定是不对称的肯定与否定不对称.问题π与π的补问题πc.π: 对于给定的实例I，X是否成立?πc: 对于给定的实例I，X是否不成立?Dπ=Dπc, Yπ=Dπc－Yπc, Yπc=Dπ－Yπ.π∈P ⇒πc∈Pπ∈NP ⇒πc∈NP? 不一定π∈P ⇔πc∈P证设M是解π的DTM程序, 则对任意I∈Dπ, M都停机. M有两个停机状态Yes和No. 设M’完全模拟M的动作, 只是交换两个停机状态.则M’是解πc的DTM程序, 因为M’停机No ⇔M停机Yes ⇔I∈Yπ⇔I∈Dπc－YπcM’停机Yes ⇔M停机No ⇔I∈Dπ－Yπ⇔I∈Yπc所以π∈P ⇒πc∈Pπc∈P ⇒π∈P.π∈NP ⇒πc∈NP ?π∈NP, 存在解π的非确定型算法. 要想得到解πc的非确定型算法必须对I∈Yπc的实例做猜想. 而I∈Dπ－Yπ⇔I∈Yπc,对于I,原来解π的非确定型算法可能根本不停机, 因此不能由这个解π的非确定型算法得到解πc的非确定型算法.(2) 形式描述}P={L:存在多项式时间的DTM程序M使得L=LM}NP={L:存在多项式时间的NDTM程序M使得L=LM非形式描述形式描述判定问题π语言L实例I∈Dπ符号串x肯定实例I∈Yπ符号串x∈LM实例规模符号串长度确定型算法对所有输入停机的DTM程序确定型算法对I回答Yes DTM程序对符号串x停机接受状态确定型算法求解判定问题πDTM程序识别语言L多项式时间的确定型算法多项式时间的DTM程序π∈P(问题类) L∈P (语言类)3. P与NP的关系P ⊆NPP = NP ?可以证明DTM模拟NDTM的时间为指数时间DTM模拟NDTM的时间复杂性的上界.定理2 P ⊆NP是多项式时间的识别L的DTM程序. 如证任取L属于P, 令M1.下构造识别L的NDTM程序M2对于给定的输入, 任意写下猜想串, 然后在检查阶段模拟M1的动作即可. 易见M是识别L的NDTM程序, 故L属于NP.2定理3 如果L∈NP, 那么存在多项式P使得L能用时间复杂性函数为O(2P(n)) 的DTM程序识别.证L∈NP, 存在识别L的NDTM程序M, 即存在多项式q, 对于任意x∈L,|x|=n, 都存在猜想串s, |s|≤q(n), M对x和s 的计算在q(n)步停机yes.长度不超过q(n)的猜想串, 至多有K q(n)个, K=|Γ|.如下构造DTM程序M’: 依次写下所有长度不超过q(n)的猜想串s, 对输入x和s使用M的检查阶段的动作进行计算. 如果对某个猜想串s, M在q(n)步内停机Yes, 则M’停机Yes; 如果M对所有的猜想串在q(n)步或停机No,或不停机, 则M’停机No. 易见LM’= LM.考虑M’的时间复杂性. 对每个猜想串的计算时间至多为q(n), 对所有猜想串的计算时间至多为O(K q(n)q(n)) = O(2P(n))三、多项式变换和NP完全性1. 多项式变换的定义（1）非形式的定义设判定问题π1, π2, 若存在函数f: Dπ1→Dπ2满足I. f可以用确定型算法在多项式时间计算II. ∀I∈Dπ1, I∈Yπ1⇔f(I)∈Yπ2则称π1可多项式变换到π2, 记作π1∝π2.构造多项式变换的步骤：针对原来问题的参数给出变换规则f: Dπ1→Dπ2证明I∈Yπ1⇔f(I)∈Yπ2证明计算f的时间为多项式时间一个多项式变换的实例例HC αTSπ1: 哈密顿回路问题HCπ2: 巡回售货员问题TSHC 实例: 图G=(V,E), V={v1,v2, ...,vm}问: G中是否包含一条哈密顿回路?TS 实例：城市集合C={c1,c2,…,cm},正整数d(ci,cj)，1≤i<j≤m，B为正整数问：是否存在一条长度不超过B的巡回路线？多项式变换 f 如下：令城市集合C=V. B=m.∀vi ,vj∈V (i≠j),⎩⎨⎧∉∈=EvvEvvvvdjijiji},{2},{1),(证明肯定实例当且仅当变换到肯定实例假设G存在一条HC <v1,v2,...,vm>, 则<v1,v2,...,vm> 也是f(G)中的旅行路线. 易见该旅行路线中的每条边长度都是1, 总长为m. 所以f(G)为TS的肯定实例.假设<v1,v2,...,vm>是f(G)中长度不超过m的旅行. 由于任何城市间的距离为1或2, 总共有m个距离, 因此每个距离必为1. 从而证明了G是HC的肯定实例.证明变换的时间为多项式时间计算d(vi ,vj), i j. 共计算m(m－1)/2次, 每次要检查{vi ,vj} 是否属于E (可以用邻接表进行). 显然是多项式时间.2）形式定义设∑1,∑2为字母表, L1⊆∑1*, L2⊆∑2* 是语言, 如果f: ∑1*→∑2*满足:I. 存在计算f的多项式时间的DTM程序II. ∀x∈∑1*, x∈L1⇔f(x)∈L2则称f是从L1到L2的多项式变换, 记作L1∝L2.所谓多项式时间的DTM程序M计算函数f : ∑*→Γ*是指:输入字符表为∑, 带字符表为Γ. M对∑*上的所有长度为n的字符串在n的多项式步内停机，且f对于任何x∈∑*, f(x)是输入x到M停机时带方格1到最右边的非空白方格为止的符号串.若L1∝L2, L2∝L1, 则称L1与L2是多项式等价的.2. 多项式变换的性质（1）若L1∝L2, 则L2∈P ⇒L1∈P.（2）若L1∝L2, L2∝L3, 则L1∝L3.证明思路条件：多项式变换f⇒存在计算f的多项式时间的DTM程序L∈P ⇒存在识别L的多项式时间的DTM 程序结论：语言属于P方法——构造识别语言的多项式时间的DTM程序存在多项式变换方法——给出多项式变换证明：若L 1∝L 2, 则L 2∈P ⇒L 1∈P证设∑1,∑2是L 1和L 2的字符表,f: ∑1*→∑2*是从L 1到L 2的多项式变换, M f 是计算f 的多项式时间的DTM 程序, M 2是识别L 2的多项式时间的DTM 程序.如下构造识别L 1的多项式时间的DTM 程序M ’: M ’首先模拟M f ,对x ∈∑1*计算出f(x)∈∑2*. 接着模拟M 2,确定f(x)是否属于L 2.因为f 是多项式变换, 即x ∈L 1 ⇔f(x)∈L 2，所以M 2对f(x)停机q Y ⇔M ’对x 停机q Y从而证明M ’识别L 1.设M f ,M 2的时间复杂性函数分别为多项式P f ,P 2,则|f(x)|≤P f (|x|)从而M ’的时间复杂性为O(P f (|x|)+ P 2(P f (|x|)))即L 1∈P.2. NP完全性若L∈NP, 且对于任意语言L’∈NP 都有L’∝L, 则称L是NP完全的, 记作L∈NPC, 其中NPC 是NP完全的语言类.类似可以定义NPC 为NP完全的问题类.3. NP完全的性质（1）若L1,L2∈NP, L1∈NPC, 且L1∝L2, 则L2∈NPC.（2）若L∈NPC, 则L∈P ⇒P = NP.（3）若P ≠NP, 则NPC⋂P=∅.证明留作思考.四、Cook定理1. 可满足性问题(1) 几个概念布尔变量的集合: U={u1,u2,...,um},ui为布尔变量U上的文字: 对于u U, u或 称为U上的文字U上的子句c: U上若干文字的集合，表示这些文字的析取.例如{u1,u3,u5}表示u1+u3+u5U上的子句集C: U上的字句的集合，表示C中子句的合取.例如C={{u1,u3,ū5},{u2,u3,ū5},{u5}}表示(u1+u3+ū5)(u2+u3+ū5)(u5)U上的真值赋值：函数t: U→{T,F}t(u)=F, 称u是假值,t(u)=T, 称u是真值.易见t(u)=T ⇔t(ū)=Ft满足子句c: c中至少有一个文字在这个赋值t下取真值t满足子句集C: t满足集合C中的每个子句.(2)可满足性问题(SAT)实例: 布尔变量集合U以及U上的子句集C问: 是否存在满足C的真值赋值?Cook定理(1971) 可满足性问题SAT是NP完全的.证(1)SAT NP.如下设计解SAT的非确定型算法. 任意猜想一个关于U中变量的真值赋值, 然后检查这个赋值是否满足C中所有的子句。
