我对计算复杂性的一些理解（论文）数媒1204陈志伟 指导老师：张军一、浅谈图灵机1、图灵机基本模型基本图灵机有一条带作为存储装置和一个控制器，控制器带一个读写头（又叫做带头）。带的两端是无穷的，被划分成无穷多个小方格，每个小方格内可以存放一个符号，控制器有有穷个状态。在计算的每一步，控制器总处于某个状态，读写头可左移或右移扫描一个方格，根据控制器当前所处的状态和读写头扫描的方格内的符号。控制器完成下列三个动作中的其中一个：1.改写被扫描方格的内容，控制器转换到一个新的状态；2.读写头向左移动一格，控制器转换到一个新的状态；3.读写头向右移动一格，控制器转换到一个新状态；结构如图所示： 左右无穷的带 读写头控制器2、图灵机形式化定义，图灵机的接受过程及接受语言过程定义：一个基本图灵机M定义为一个七元组 TM=Q,C,A,B,q1,F。Q是状态集，一个非空有穷集合，标示图灵机的所有状态；C是带字母表，（放在带方格中的符号集合）非空有穷集；是动作函数，包括控制函数或过程转换函数（定义控制器），是QxCQxC（R,L）的部分函数；A是输入字母表，AC-B；B是空白符，BC；q1是初始状态，q1Q；F是接收状态集，F Q，F中的元素叫做接收状态图灵机的每一步计算由动作函数确定，设当前状态q,被扫描的符号为s（q，s）=（q,s），把被扫描的方格的内容改写成s并且转换到状态q，读写头的位置保持不变。（q，s）=(q,R)，读写头左移一格并且转换到状态q，带的内容保持不变。（q，s）=(q,L)，读写头右移一格并且转换到状态q，带的内容保持不变。（q，s）无定义，则停止计算。图灵机的格局包括带的内容、读写头的位置和控制器的状态，可表示成：a1a2a3aj-1qajaj+1其中qQ，aiC；它表示的内容是a1a2a3ak，两端其余部分全是B，读写头正在扫描aj，控制器处于状态q。如果（q，aj），则称这个格局是停机格局。如果停机格局中的状态是接收状态，则称这个格局是接受格局。定义图灵机接受过程：如果从初试格局q1Bx开始计算，图灵机最终停机在接受格局，则称图灵机接收x。图灵机接收的所有字符串组成的集合称作图灵机接收的语言，或图灵机识别的语言。3、图灵机其他形式（1） 五元图灵机五元图灵机的一步要做四元图灵机两步做的事情，改写一个符号并且左移一格，或者改写一个符号并且右移一格。 （2） 单向无穷带图灵机单项无穷带图灵机的带仅在一个方向上是无穷的，有一个最左方格#被固定在带的左端，他左边的方格永远不会被使用。（3） 多带图灵机 多带图灵机有k个读写头，没个读写头扫描一条带，可以改写被扫描方格内的符号、左移一格或者右移一格。读写头的动作由当前的状态和k个读写头从k条带上读到的k个符号决定。（4） 离线图灵机 离线图灵机有一条输入带和k条工作带，输入带的带头只读不写，工作带的带头是和普通多带图灵机一样的读写头。# $分别表示输入带的左端和右端。4、各种图灵机之间关系定理：四元图灵机与五元图灵机是等价的。 定理：单向图灵机与四元机是等价的。定理：多带图灵机与单带图灵机是等价的。定理：离线图灵机与单带图灵机是等价。总结：图灵机都是等价的。二、不可判定问题及相关结论，图灵机停机判定问题，文法不可判定问题 1、不可判定问题及结论设判定问题，使为真的实例的集合为Y，实例的全体集合为D，这样一个判定问题就可以这样描述=（D，Y）。通过二元组编码和谓词对应来讨论。通过编码建立判定问题与谓词的对应关系设编码为e，DA*(谓词)。对于ID，D（I）IY，其中e（I）=x对于同一个判定问题，其编码e1与e2得谓词P1与P2，根据chuuring-Turing命题，若e1与e2是可计算的，则有可计算函数 f1: A *A*; f2: A *A*使得P1(x)P2(X) P2(X) P1(x)。定义：如果谓词是可计算的，则称判定问题是可判定的，如果谓词是半可判定的，则称判定问题是半可判定的，否则是不可判定的。定义：设1与2两个判定问题，若有函数f：D1 D2满足：(1)f是可计算的；(2)对于每个实例ID1总有IYf（I）Y2 则称f为判定问题1到2的规约。定理：设判定问题1可规约为判定问题2，则2是可判定的，蕴含1是可判定的；2是不可判定的，蕴含1是不可判定的。（1）图灵机停机判定问题定义：图灵机的停机问题任给图灵机和格局，从格局开始，图灵机是否最终停机？定理：图灵机的停机问题是不可判定的。（2）文法不可判定问题引理：如果uL(M),则L()=,如果u不属于L(M),则L()=空集定理：下述问题是不可判定的：任给一个文法G，是否L(G)为空集？任给一个文法G，是否L(G)是无穷的？任给一个文法G和字符串x，是否xL(G)？2、 正则语言（1）chomsky文法分类 文法为四元组G=（V，T，P，）其中，V为非终结符集合，T为终结符集合，P为规则集，为开始符号0型文法：等价于图灵机。对产生式不附加任何条件。1型文法：线性界限自动机。是上下文有关文法，每一个产生式都满足条件|2型文法：下推自动机。是上下文无关文法，每一个产生式都形如A，其中AV，(TU)* 3行文法：有穷自动机。正则文法，若文法满足AaB或Aw,其中A，BV，wA*，则称此种文法为右线型文法；若ABa，A Aw,其中A，BV，wA*,则称此种文法为左线型文法。（2）DFA，NFA正则定义及相关结论确定自动机DFA M=（Q,A, ，q1,F）其中 Q是状态集；A是输入字母表；q1是初态，q1Q；F是终态集， F Q； 是控制函数或者转换函数，：QxAQ , 是确定的。Q=q1，q2，q3，q4；A=a,b F=q3则根据状态转化图得知 L（G）=bna / n1.不确定自动机NFA M=（Q,A, *，q1,F），其中 Q是状态集；A是输入字母表；q1是初态，q1Q；F是终态集， F Q；是控制函数或者转换函数，*：QxA*2Q根据状态转化图得知 L（G）=an / n2bna / n1DFA与NFA仅仅是控制函数的不同。结论：不确定自动机和确定自动机是等价的。定理：语言L能被DFA接受当且仅当语言L能被NFA接受。定理：语言L是正则语言当且仅当存在DFA M使L=L(M)。三、非正则语言的定义及相关结论（1）泵引理内容及主要作用正则语言的泵引理：设L是正则语言，则存在与L相关的常数n满足：对于任何L中的串w，如果|w|n，则我们就能够把w打断为三个串w=xyz使得：（1）y 。（2）|xy| n。（3）对于所有的k 0，串xykzL。换句话说，我们总能够在离w的开始处的地方找到一个非空的串y，然后可以把它作为“泵”，也就是说，重复y任意多次，或者去掉它（k=0的情况），而所得到的结果串仍然输入L。泵引理作用：Pumping引理揭示了正则语言普遍具有的这样一个封闭性质：如果L是一个正则语言，那么存在一个正整数k, L中那些长度 k的句子中，都含有这样的一段子串，把这个子串重复任意多次后形成的句子仍然是L中的语句。应用泵引理可以辨别出非正则语言。四、上下文无关文法1、chomsky范式的文法及相关理论（等价性）chomsky范式文法：设上下文无关文法G=(V ,T,P,S)的每一个产生式都有如下形式：xyz，xa 其中x，y，zV，aT，则上下文无关文法G为chomsky范式文法。定义：设正上下文无关文法G=(V ,T,P,S)，形如XY的产生式称作单枝的，其中X,YV。如果G不含单枝的产生式，则称它是分枝的。定理：G为上下文无关文法，则存在分枝的正的上下文无关文法G使L(G)=L(G)2、Bar-Hillel泵引理及主要作用Bar-Hillel泵引理:设chomsky范式文法有n个变元，L=L(G)，对于xL，若|X|2n则x可以表示成x=u1v1uv2u2，使得（1）|v1uv2|2n；（2）|v1v2|；（3）对于所有的k0，u1v1kuv2k u2L推论：设L是上下文无关语言，则存在正整数m，使得长度大于m的x可用于验证某些语言不是上下文无关语言。作用：通过泵引理以反证法证明L不是上下文无关语言。五、时间复杂性及空间复杂性理论1、用图灵机定义的时间复杂性与空间复杂性相关概念及有关结论时间复杂度定义：设DTM M，对于所有的wA*，M总停机，把M对w的计算步骤数记为tm（w）称M关于w的计算时间，称tm(n)=maxtm(w)/wA*且|w|n，nN称为图灵机M的时间复杂度。设t：nN,r如果tm(n)= (t(n)，称t(n)是图灵机M的时间复杂度上界。定理：设M是一个t(n)时间上界的多带图灵机，则存在t2(n)时间上界的单带图灵机M使L(M)=L(M)。这里的M可以是DTM，也可以是NTM，但是它是多带的，M的时间上界是t(n)。M是单带，可以是DTM，也可以是NTM，M的时间上界是t2(n)。空间复杂度定义：设DTM M，字母表为A，对所有的wA*，M总停机，把M关于w的计算中在每一条工作带上使用的方格数的最大值记为.称=max,nN 为M的空间复杂度。设全函数s:NN。如果=O(s(n)，则称s(n)是M的空间复杂度上界。定理：设M是一台有k条工作带的s(n)空间界限的离线DTM(NTM)，其中k1，则存在只有一条工作带的离线DTM(NTM)M，使得L(M)=L(M)并且M与M有相同的空间复杂度上界。六、NP完全性理论1、多项式的时间变换和NP完全性的相关定义及结论定义：设字母表A，L1，L2A*，如果函数f：A*A*，满足条件：（1）f是多项式可计算的，即存在DTM M和多项式P，使对任意xA*，M在P|x|步内停机且输出f（x）；（2）任意xA*，xL1f(x)L2,则称f是L1到L2的多项式时间变换，或者多项式时间映射规约。如果存L1到L2的多项式时间变换，则称L1可多项式时间变换到L2，记作L1mL2。定义：设判定问题1=（D1，y1）, 2=（D2，y2）,若函数f：D1D2满足：（1）f是多项式可计算的（2）任意ID1, IY1f（I）Y2则称f是1到2的多项式时间变换。定理1：设L1mL2，L2mL3，则L1mL3定理2：设L1mL2，则有，(1)若L2P，则L1P；(2)若L2NP，则L1NP2、Cook定理的内容，证明及意义S.A.Cook于1971年给出第一个NP完全问题，这是数理逻辑中的一个问题。取全功能集,，其中是合取联结词、是析取联结词、是否定联结词，由变元、圆括号和联结词组成的表达式称作合式公式。变元和它