第十三章计算复杂性.

第十三章计算复杂性13.1计算模型13.2复杂性类型之间的关系13.3归约性关系13.4完备性13.1计算模型13.1.1图灵机的基本模型13.1.2k带图灵机和时间复杂性13.1.3离线图灵机和空间复杂性13.1.4可满足性问题和Cook定理13.1.1图灵机的基本模型一、字母表、符号串和语言1、字母表：非空的有穷符号集合，记为。2、符号串：由符号组成的有穷序列，上的所有符号串的全体记为*。3、语言：由中的符号按照一定规则构成的长度有限的符号串集合，记为L。把问题实例的描述译按照一定规则码成一个有穷的符号串集合，这些符号串集合称为语言L例：母表为}),(,1,0{图),(EVG，},,2,1{nV，用下面的符号串描述它的邻接矩阵：),,,(),,,(),,,()(212222111211nnnnnnxxxxxxxxxG其中，如果Eji),(，则1ijx，否则，0ijx。13.1.1图灵机的基本模型二、图灵机1、图灵机的构成图灵机由一个控制器和一条无限长的工作带组成，如图13.1所示。┅┅Ba1a2┅┅anB┅┅读写头有限状态控制器图13.1图灵机示意图工作带：划分为许多单元，每个单元可以存放字母表中的一个符号。控制器：具有有穷个内部状态和一个读写头。13.1.1图灵机的基本模型2、图灵机的工作过程计算的每一步，控制器处于某个状态，读写头扫描工作带的某一个单元符号；根据当前状态、被扫描单元的内容，决定下一步的执行动作：把当前单元内容，改写成某一个符号；使读写头停止不动、向左或向右移动一个单元；使控制器转移到某一个状态等等。计算开始时，输入符号串放在工作带上，控制器处于初始状态0p，读写头扫描输入符号串左端的第一个符号；如果对于当前的状态和所扫描的符号，没有下一步的动作，则图灵机就停止计算。13.1.1图灵机的基本模型3、图灵机的形式定义定义13.1图灵机M是一个六元组：),,,,,(0fppSM，其中：(1)S：控制器的非空有限状态集合；(2)：有限的工作带符号集合，包括空白符B；(3)：输入符号字母表，}{B；(4)0p：初始状态，Sp0；(5)fp：最终状态或接受状态，Spf；(6)：转移函数，它把S的某一个元素，映射为},,{)}{(RPLBS中的元素。13.1.1图灵机的基本模型4、转移函数的说明1）转移函数的定义域：Sdom)(2）转移函数的值域：},,{)}{()(RPLBSran3）},,{RPL：读写头的动作L左移一个单元；P停止不动；R右移一个单元；4）转移函数的含义：),','(),(Rxpxp控制器当前状态为p、读写头扫描到的符号为x时，图灵机执行的动作为：把控制器状态修改为'p；把符号修改为符号'x；使读写头向右移动一个单元。13.1.1图灵机的基本模型二、图灵机的格局1、图灵机的格局描述计算中每一步控制器所处的状态，及读写头的位置。2、图灵机格局的定义定义13.2令),,,,,(0fppSM是一个图灵机，M的格局是一个二元组：),(21p其中，Sp，表示图灵机在此格局下控制器的状态；21,是工作带上的内容。表示在此格局下读写头的位置；1表示处于读写头左边的符号串；2表示处于读写头右边的符号串。读写头指向符号串2的第一个符号。),(00p，表示图灵机M的一个初始格局，此时，1为空串；13.1.1图灵机的基本模型3、可接受格局：格局),(21p中的p是可接受状态，即fpp，则称是可接受格局；4、停机格局格局),(21p中，2的第一个符号是x，转移函数),(xp没有定义，则称是停机格局。13.1.1图灵机的基本模型三、图灵机的计算1、图灵机的计算：,,,,21n是一个有穷、或无穷的格局序列，如果每一个1i都由i经过一步得到，就称这个序列是一个计算。2、图灵机计算的停机状态1）计算是有穷序列n,,,10，n是可接受的停机格局，称停机在接受状态。称图灵机M接受符号串；2）计算是有穷序列n,,,10，n不是可接受的停机格局，称停机在拒绝状态。称图灵机M不接受符号串，或拒绝符号串3）计算是无穷序列,,,,21n，永不停机。13.1.1图灵机的基本模型3、图灵机对语言的识别定义13.3若符号串*，图灵机M接受符号串，有}|{)(*接受MML则称图灵机M接受语言)(ML，或图灵机M识别语言)(ML。13.1.1图灵机的基本模型例构造一个识别语言}1|{nbaLnn的图灵机。思想方法：使读写头来回移动，成对地对输入符号串左端的a和右端的b作标记。如果的全部符号都作了标记，则左边的a与右边的b个数相等，L；否则，L。13.1.1图灵机的基本模型图灵机),,,,,(0fppSM的构造：},,,,,{43210NppppppS；},,,{Bxba；},{ba；},{4Nfppp；转移函数),(p如表13.1所示，其中，4p为接受状态，Np为拒绝状态。表13.1),(p转移函数表abxB0p),,(0Rap),,(1Lxp1p),,(2Rxp),,(1Lxp),,(RBpN2p),,(1Lxp),,(2Rxp),,(3LBp3p),,(RapN),,(3Lxp),,(4RBp4pNp13.1.1图灵机的基本模型2n，图灵机的工作过程如下：图灵机的格局应执行的动作图灵机的格局应执行的动作),(00aabbBBp，),,(0Rap),(01abbBBap，),,(0Rap),(02bbBBaap，),,(1Lxp),(13xbBBaap，),,(2Rxp),(24xbBBaxp，),,(2Rxp),(25bBBaxxp，),,(1Lxp),(16xBBaxxp，),,(1Lxp),(17xxBBaxp，),,(1Lxp),(18xxxBBap，),,(2Rxp),(29xxxBBxp，),,(2Rxp),(210xxBBxxp，),,(2Rxp),(211xBBxxxp，),,(2Rxp),(212BBxxxxp，),,(3LBp),(313BBxxxxp，),,(3Lxp),(314xBBxxxp，),,(3Lxp),(315xxBBxxp，),,(3Lxp),(316xxxBBxp，),,(3Lxp),(317xxxxBBp，),,(4RBp),(418xxxxBBp，13.1.2k带图灵机和时间复杂性一、k带图灵机1、k带图灵机：有k个工作带，每个工作带有一个读写头，都可以独立地移动。13.1.2k带图灵机和时间复杂性2、k带图灵机的形式定义1）形式定义定义13.4k带图灵机M是一个六元组：),,,,,(0fppSM，其中(1)S：控制器的非空有限状态集合；(2)：有限的工作带符号字母表，包括空格符B；(3)：输入符号字母表，}{B；(4)0p：初始状态，Sp0；(5)fp：最终状态或接受状态，Spf；(6)：转移函数，把kS的某一个元素，映射为kRPLBS)},,{)}{(中的元素。13.1.2k带图灵机和时间复杂性2）转移函数的定义域：kSdom)(3）转移函数的值域：kRPLBSran)},,{)}{(()(4）转移函数的形式：)),(,,),(,),(,'(),,,,('2'21'121kkkDxDxDxpxxxp表示在控制器当前状态为p、读写头i扫描到的符号为ix时，对所有的i，ki1，RPLDi,,图灵机执行的动作为：控制器状态p修改为'p；符号ix修改为符号'ix；读写头i按iD方向移动一个单元。13.1.2k带图灵机和时间复杂性3、k带图灵机的格局定义13.5令),,,,,(0fppSM是一个k带图灵机，M的格局是一个1k元组：),,,,(2122211211kkpSp：图灵机在此格局下控制器的状态；21ii：第i个工作带上的内容。若x是输入符号串，则初始格局表示为),,,,(0BBxp13.1.2k带图灵机和时间复杂性二、确定性图灵机和非确定性图灵机1、确定性图灵机1）定义定义13.6如果图灵机M的转移函数是单值的，则称该图灵机为确定性图灵机，记为DTM。2）特性函数把kS中的一个元素，映射为kRPLBS)},,{)}{((中的一个元素。图灵机每一步的动作都是确定的。13.1.2k带图灵机和时间复杂性2、非确定性图灵机1）定义定义13.7如果图灵机M的转移函数是多值的，则称该图灵机为非确定性图灵机，记为NDTM。2）特性：函数把kS中的一个元素，映射为kRPLBS)},,{)}{((中的一个子集，图灵机可以从子集中挑选一个元素作为它的函数值。0)2(cncNTIMENEXPTIME13.1.2k带图灵机和时间复杂性三、图灵机的执行时间1、图灵机的计算的长度定义13.8设t,,,21是一个格局序列，它是图灵机对输入x的一个计算。如果t是一个可接受的停机格局，则称这个计算是可接受的计算，t称为这个计算的长度。2、图灵机的执行时间定义13.9图灵机M对输入x进行计算的执行时间，记为)(xTM，它定义为：(1)如果M对输入x有一个可接受的计算，则)(xTM是最短的可接受计算的长度；(2)如果M对输入x没有一个可接受的计算，则)(xTM。13.1.2k带图灵机和时间复杂性四、语言的时间复杂性定义1、语言的时间复杂性定义L是一个语言，f是从非负整数集到非负整数集的函数。若存在确定性的图灵机DTM（或非确定性的图灵机NDTM），使得对输入x，若Lx，则)||()(xfxTM；否则)(xTM。就说，L是属于)(fDTIME中的（或处于)(fNTIME中）的语言。2、P类问题的形式定义)()()(2knDTIMEnDTIMEnDTIMEP等价于}|{所识别在多项式时间内被DTMLLP例：在例13.1中，若输入符号串是可接受的，对某个常数0c，工作带读写头的移动次数将小于或等于2nc。则，}1|{nbaLnn是属于)(2nDTIME的语言。13.1.2k带图灵机和时间复杂性例构造识别语言}}1,0{|{*RcL的图灵机。其中，字符串R是字符串的逆串。图灵机工作过程：1、令M是二带的图灵机，它有一个输入带和一个工作带。2、M从左到右扫描输入带，把输入带内容拷贝到工作带，直到输入带读写头到达符号c为止3、输入带读写头继续向右移动，每读入一个符号，就和工作带读写头所指单元的符号比较，4、若相同，工作带读写头左移一单元，输入带读写头右移一单元，继续读入下一字符，并进行上述比较工作。5、这个过程直到所有输入处理完毕。6、如果符号c两旁的符号个数相同，并在上述处理过程中，两旁的符号互相匹配，则M接受语言L，否则拒绝。13.1.2k带图灵机和时间复杂性时间分析：如果输入长度为n，输入带读写头移动n次，工作带读写头移动1n次。因此，语言}}1,0{|{*RcL是属于)(nDTIME的语言。13.1.2k带图灵机和时间复杂性五、其它复杂性类型除了上面定义的几种复杂性类型外，还可以定义下面四种复杂性类型：0)2(ccnDTIMEDEXT0)2(ccnNTIMENEXT0)2(cncDTIMEEXPTIME0)2(cncNTIMENEXPTIME13.1.3离线图灵机和空间复杂性一、离线图灵机1、离线图灵机（off_lineTuringmachine）：两个工作带，只读输入带：用于存放输入符号串，可读可写的工作带：用于存放工作数据。2、离线图灵机的形式定义定义13.10离线