算法设计(第9章计算复杂性与NP理论)

第9章计算复杂性与NP理论,9.1多项式规约9.2计算模型9.3P和NP类问题9.4NP完全问题,9.1多项式规约,规约：如果存在两个问题Q和Q，对于Q的任何一个实例q，都能找到Q的一个实例q，并能够将q的解a转换为q的解a，则称问题Q可以被归约到问题Q,Q,Q,q,q,a,a,9.1多项式规约,规约：如果存在两个问题Q和Q，对于Q的任何一个实例q，都能找到Q的一个实例q，并能够将q的解a转换为q的解a，则称问题Q可以被归约到问题Q多项式规约：可在多项式时间内完成的规约,Q,Q,q,q,a,a,9.1多项式规约,问题示例,ax2+bx+c=0,ax3+bx2+cx+d=0,9.1多项式规约,问题示例,G=最大独立集,G=最小顶点覆盖,V/C是G的最大独立集,C是G的最小顶点覆盖,9.2计算模型,形式语言与问题编码形式语言:字母表是符号的有限集合，上的语言L是由中的符号所组成的串的任意集合,=0,1,L1=0,1,10,11,100,101,110,111,1000,1001,L2=0,10,100,110,1000,1010,9.2计算模型,形式语言与问题编码形式语言:字母表是符号的有限集合，上的语言L是由中的符号所组成的串的任意集合问题编码：问题Q的任意一个输入都会被编码为一个二进制串s。设问题的输入集合为I，其编码就是一个映射e:I0,1*,9.2计算模型,形式语言与问题编码形式语言:字母表是符号的有限集合，上的语言L是由中的符号所组成的串的任意集合问题编码：问题Q的任意一个输入都会被编码为一个二进制串s。设问题的输入集合为I，其编码就是一个映射e:I0,1*问题算法：设A是问题Q的一个算法，那么A应当接受输入s，算法运行得到的结果记为A(s)。当Q是一个判定形式的问题，则对于任意输入A(s)yes,no,9.2计算模型,图灵机在当前方格中写入新字符读写头左移(L)、右移(R)或不动(S)改变状态控制器中的当前状态,9.2计算模型,图灵机形式定义：一个七元组M=(Q,b,q0,F)，其中Q是有限状态集，是字母表，是读写带上的字符集，b是空白字符(b但b)，:QQL,R,S是动作转移函数，q0Q是初始状态，FQ是终止状态集。,9.2计算模型,图灵机M=(Q,b,q0,F)将输入符号串s=a0a1an依此填在纸带的第0,1,n号格子上，读写头指向第0号格子，机器处于状态q0当前状态qiF则停机把扫描到的符号xi传送到状态控制器，控制器再根据当前状态qi计算动作转移函数，并根据函数值决定下一步的操作,9.2计算模型,图灵机M=(Q,b,q0,F)终止状态qa表示接受输入字符串,qr表示拒绝动作转移函数允许是一个部分函数，当(qi,xi)上无定义时也将停机,9.2计算模型,图灵机M=(Q,b,q0,F)问题：判断一个二进制串中有奇数个还是偶数个1,9.2计算模型,图灵机M=(Q,b,q0,F)k带图灵机,:QkQ(L,R,S)k,9.2计算模型,图灵机M=(Q,b,q0,F)k带图灵机不确定图灵机,9.2计算模型,图灵机与可计算性设f是一个函数，如果能通过一个图灵机M来完成f的计算，则称f是部分可计算的；如果M能够完成f的计算，且对于f定义域上的任意一个输入s，M都能保证停机，则称f是可计算的，或者说f是一个可计算函数。设L是一个语言，如果它能够被一个图灵机M接受，则称L是一个递归可枚举语言；如果M能够接受L，且对于输入sL，M都能保证停机，则称L是一个递归语言。,9.2计算模型,图灵机与可计算性称语言L1可被多项式时间归约到语言L2，如果存在一个多项式时间可计算的函数f:0,1*0,1*，其对任意的x0,1*都有：xL1当且仅当xL2,9.2计算模型,一个算法就是一个确定的、对任意合法输入都停机的图灵机对于每个长度为n的输入，如果图灵机M在计算过程中的读写头移动次数不超过T(n)，则称M是以T(n)为时间上界（简称时间界）的图灵机给定一个问题Q，如果存在一个时间界为T(n)的图灵机对其进行计算，则称Q的时间复杂度为T(n),9.3P和NP类问题,P类问题：存在多项式时间算法的计算问题能够用确定性图灵机在多项式时间界内求解的问题称为P类问题P=L0,1*|存在一个确定性图灵机M能够在多项式时间内接受L,P,NP,9.3P和NP类问题,NP类问题能够用不确定性图灵机在多