计算复杂性理论总结报告

计算复杂性理论总结报告一、图灵机（1）图灵机基本模型图灵机是由图灵（AlanMathisomTuring）在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）。基本图灵机又称四元机，五元机是指把基本四元机的动作合并：qsq’Ls’即δ（q，s）=（q’,s’,L）；qsq’Rs’即δ（q，s）=（q’,s’,R）。定义基本动作不同（2）单向无穷图灵机由单带单向所限制，必须δ（q0，#）=（q1,R）；δ（q0，#）=（q1,L）无意义，不存在。（3）多带图灵机δ：QxCQxC1xC2xC3…Cnx{R,L}有多个读写头，一个控制器图2多带图灵机（4）离线图灵机离线图灵机是多带的，同时将带方格分为输入带和工作带，其中输入带始终不变，工作带是中间过程带。（4）各种图灵机之间关系定理：四元图灵机与五元图灵机是等价的。定理：单向图灵机与四元机是等价的。定理：多带图灵机与单带图灵机是等价的。定理：离线图灵机与单带图灵机是等价。总结：图灵机都是等价的。二、不可判定问题及相关结论，会图灵机停机问题，文法不可判定问题判定问题主要讨论带参数的判定问题，比如X∈N，问X是素数吗？设判定问题π，使π为真的实例的集合为Yπ，实例的全体集合为Dπ，这样一个判定问题就可以这样描述π=（Dπ，Yπ）。例如：π=（N,P），如何处理？通过二元组编码和谓词对应来讨论。通过编码建立判定问题与谓词的对应关系设编码为e，Dπ—A*(谓词)。对于I∈Dπ，Dπ（I）=I∈Yπ，其中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：Dπ1—Dπ2满足：（1）f是可计算的；（2）对于每个实例I∈Dπ1总有I∈Yπ=f（I）∈Yπ2则称f为判定问题π1到π2的规约。定理：设判定问题π1可规约为判定问题π2，则（1）π2是可判定的，蕴含π1是可判定的；（2）π2是不可判定的，蕴含π1是不可判定的。三、正则语言（1）chomsky文法分类文法的chomsky语言定义如下：文法为四元组G=（V，T，P，δ）其中，V为非终结符集合，T为终结符集合，P为规则集，δ为开始符号(1)0型文法对于规则不做任何限制，又称关于结构文法，还称无限制文法(2)1型文法又称上下文有关文法，记为CSG。要求规则α—β满足：|α|≤|β|，所形成的语言叫1型语言。(3)2型文法又称上下文无关文法，记为CFGA—α其中A∈V，α∈（V∪T）*(4)若文法满足A—aB或A—w,其中A，B∈V，w∈A*，则称此种文法为右线型文法；若A—Ba，A—A—w,其中A，B∈V，w∈A*,则称此种文法为左线型文法，或称为正则文法。举例：GS—aA，A—aA，A—bB，A—b，B—bB，B—b.V={S，A,B}，T={a，b}此文法所识别的语言为L（G）={anbm/n,m≥1}.（2）DFA，NFA正则式及相关结论确定自动机DFAM=（Q,A,δ，q1,F）其中Q是状态集；A是输入字母表；q1是初态，q1∈Q；F是终态集，F⊆Q；δ是控制函数或者转换函数，δ：QxA—Q,δ是确定的。DFA举例：Q={q1，q2，q3，q4}；A={a,b}F={q3}则根据状态转化图得知L（G）={bna/n≥1}.不确定自动机NFAM=（Q,A,δ*，q1,F），其中Q是状态集；A是输入字母表；q1是初态，q1∈Q；F是终态集，F⊆Q；δ是控制函数或者转换函数，δ*：QxA*2Qabaq1q4q3q2bab根据状态转化图得知L（G）={an/n≥2}∪{bna/n≥1}DFA与NFA仅仅是控制函数的不同。结论：不确定自动机和确定自动机是等价的。定理：语言L能被DFA接受当且仅当语言L能被NFA接受。定理：语言L是正则语言当且仅当存在DFAM使L=L(M)。（3）泵引理内容及主要作用正则语言的泵引理：设L是正则语言，则存在与L相关的常数n满足：对于任何L中的串w，如果|w|≥n，则我们就能够把w打断为三个串w=xyz使得：（1）y≠ε。（2）|xy|≤n。（3）对于所有的k≥0，串xykz∈L。换句话说，我们总能够在离w的开始处的地方找到一个非空的串y，然后可以把它作为“泵”，也就是说，重复y任意多次，或者去掉它（k=0的情况），而所得到的结果串仍然输入L。泵引理作用：Pumping引理揭示了正规语言普遍具有的这样一个封闭性质：如果L是一个正规语言，那么存在一个正整数k,L中那些长度k的句子中，都含有这样的一段子串，把这个子串重复任意多次后形成的句子仍然是L中的语句。应用泵引理可以辨别出非正规语言。四、上下文无关文法（1）chomsky范式的文法及相关理论chomsky范式文法：设上下文无关文法G=(V,T,P,S)的每一个产生式都有如下形式：x—yz，x—a其中x，y，z∈V，a∈T，则上下文无关文法G为chomsky范式文法。定理：G为上下文无关文法，则存在正的上下文无关文法G’使L(G)=L(G’)abaq1q4q3q2aab（2）Bar-Hillel泵引理及主要作用Bar-Hillel泵引理:设chomsky范式文法有n个变元，L=L(G)，对于x∈L，若|X|≥2n则x可以表示成x=u1v1uv2u2，使得（1）|v1uv2|≥2n；（2）|v1v2|≠ε；（3）对于所有的k≥0，u1v1kuv2ku2∈L推论：设L是上下文无关语言，则存在正整数m，使得长度大于m的x可用于验证某些语言不是上下文无关语言。作用：通过泵引理以反证法证明L不是上下文无关语言。五、时间复杂性及空间复杂性理论（1）用图灵机定义的时间复杂性与空间复杂性相关概念及有关结论时间复杂度定义：设DTMM，对于所有的w∈A*，M总停机，把M对w的计算步骤数记为tm（w）称M关于w的计算时间，称tm(n)=max{tm(w)/w∈A*且|w|≤n，n＜N}称为图灵机M的时间复杂度。设t：n—N,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)。空间复杂度每一条工作带上使用的带方格的最大值为Sm（w），称Sm（n）=max{Sm(w)/w∈A*且|w|≤n}为图灵机的空间复杂度。同样的，设t：n—N,r如果Sm(n)=Ο(S(n))，称S(n)是图灵机M的空间复杂度上界。定理：设M是一个又k条工作带的Sm（n）空间界限的离线TDM（NTM），其中k＞1，则存在只有一条工作带的离线图灵机TDM（NDM）M’，使L(M)=L(M’)且M与M’有相同的空间复杂度。（2）计算复杂性类的相关定义及相关结论定义1：如果存在t(n)时间界限的DTM接受语言L，则称L是Ο(t(n))的时间可识别的；如果存在t(n)时间界限的NTM接受语言L，则称L是非确定型Ο(t(n))的时间可识别的。如果存在S(n)空间界限的DTM接受语言L，则称L是Ο(S(n))的空间可识别的。如果存在S(n)空间界限的NTM接受语言L，则称L是非确定型Ο(S(n))的空间可识别的。DTIME(t(n))={L/L是Ο(t(n))的时间可识别的};NTIME(t(n))={L/L是Ο(t(n))非确定型时间可识别的};DSPACE(S(n))={L/L是Ο(S(n))的空间可识别的};NSPACE(S(n))={L/L是Ο(S(n))非确定型空间可识别的};定义2：多项式时间可识别的语言类：P=∪DTIME(nk)；非确定型多项式时间可识别的语言类：NP=∪NTIME(nk)；指数时间可识别的语言类：EXPTIME=∪DTIMEαΟ(nk)非确定型指数时间可识别的语言类：NEXPTIME=∪NTIMEαΟ(nk)对数空间可识别的语言类：L=DSPACE（logn）；非确定型对数空间可识别的语言类：NL=NSPACE（logn）；多项式空间可识别的语言类：PSPACE=∪DSPACE（nk）；非确定型多项式空间可识别的语言类：NSPACE=∪NSPACE（nk）；指数空间可识别的语言类：EXPSPACE=∪DSPACEαΟ(nk)非确定型指数空间可识别的语言类：NEXPSPACE=∪NSPACEαΟ(nk)定义3：设f：N—N，如果存在一台发f（n）空间界限的DTMM使对每一个输入，M的输出是f(n)的二进制表示，则f是空间可构造的。引理：设S是空间可构造的，S(n)≥log（n），则存在DTMM对任意长为n的输入，使用Ο(S(n))空间，在Ο(S(n))步内在工作带上标明S(n)个带方格。定理：设S是空间可构造的，且S(n)≥log（n），对L∈NSPACE(S(n))，则存在常数c＞0，使得L∈DTIMEαΟ(nk)定理：设S是空间可构造的且S(n)≥log（n），M是一台S(n)空间界限的NTMM。则存在S2(n)空间界限的DTMM’,使L(M)=L(M’)。（3）计算复杂性类的包含的相关结论L⊆NL⊆P⊆PSPACE⊆EXPTIM⊆NEXPTIM⊆ExPSPACEP⊂NL⊂PSPACE⊂EXPTIME定理：设S2（n）是一个空间可构造函数，S1（n）≥logn，S2（n）≥logn，且limS1（n）/S2（n）=0,则存在一个语言，它在DSPACE（S2（n））中，但是不在DSPACE（S1（n）），DSPACE（S1（n））⊂PSPACE（S2（n））。六、NP完全性理论（1）多项式的时间变换和NP完全性的相关定义及结论多项式时间变换定义：设字母表A，L1，L2∈A*，对f：A*A*，若满足：（1）f是多项式可计算的，即存在DTMM和多项式P，使对任意x∈A*，M在P1|x|步内停机，输出f（x）；（2）任意x∈A*，