定理证明例题.doc

定理 设t(n)是一个函数，t(n)=n,则每一个t(n)时间的多带图灵机都和某一个O(t2(n)时间的单带图灵机等价设t(n)是一个函数，t(n)=n,则每一个t(n)时间的非确定型单带图灵机都与某一个2 O(t(n)时间的确定型单带图灵机等价定义 P是确定型单带图灵机在在多项式时间内可判定的语言类，换言之：P= 1）对于所有与确定型单带图灵机多项式的等价的计算模型来说，P是不变的2）P大致对应于在计算机上时即可解的那一类问题定理PATH属于P证明 PATH的一个多项式时间算法M运行如下：M=“对输入,G是包含结点s和t的有向图：1)在结点s上做标记2）重复下面步骤3，知道不再有节点被标记3）扫描G的所有边，如果找到一条边(a,b),a被标记而b没有标记，那么标记b4）若t被标记，则接受；否则，拒绝”分析该算法，证明他在多项式时间内运行，显然，步骤1和4只执行一次，步骤3最多执行m此，因为出最后一次外，每一次执行都要标记G中的一个未标记的结点，所以用到的总步骤数最多是1+1+m，是G的规模的多项式，M的步骤1和4很容易用任何合理的确定型模型在多项式时间内实现，捕捉3需要扫描输入，检查某些结点是否被标记，这也容易在多项式时间内实现，所以M是PATH的多项式时间算法定理 RELPRIME属于P 欧几里德算法证明 欧几里德算法E如下：E=“对输入，x和y是二进制表示的自然数：1）重复下面的操作，知道y=0 2）赋值xx mod y3）交换x和y的值 4）输出x”算反R以E为子程序求解RELPRIME，R=”对输入x和y是二进制表示的自然数： 1）在上运行E， 2）若结果为1，就接受；否则，就拒绝”显然，若E在多项式时间内运行且正确，则R也在多项式时间内运行且正确，所以只需分析E的时候和正确性，步骤2的每一次执行（除了第一次有可能例外）都把x的值至少减少一半，执行步骤2以后，由函数mod的性质知xy因为这两个值已经交换，于是当步骤2随后执行时有xy，若x/2=y,则x mod yy=x/2，x至少减少一半，若x/2y，则x mod y=x-yx/2,x至少减少一半，每一次执行步骤3都是x和y的值相互交换，所以每两次循环就使得x和y原先的值至少减少一半，于是步骤2和4执行的最大次数是2log2x和2log2y中较小的那一个，这两个对数宇表示的长度成正比，步骤的执行次数是O(n)，E的每一步消耗多项式时间，所以整个运行时间是多项式的根号nnnloglognnlognn2c正则的上下文无关的可判定的图灵可识别的定理：ADFA是一个可判定语言证明：首先检查输入，他表示输入串w和DFA B，B的一个合理的表示方法是简单地 列出它的五个元素Q,q0及F，当M收到输入时，首先检查他是否正确地表示了DFA B和串w，如果不是，则拒绝。然后M直接执行模拟，用在带上写下信息的方法，他可以跟踪B在输入M上运行时的当前状态和当前位置，运行开始时，B的当前状态时q0，读写头的当前位置是w的最左端符号，状态和位置的更新是由转移函数决定的，当M处理完w的最后一个符号时，如果B处于接受状态，则M接受这个输入，如果不是，则M拒绝定理：ANFA是一个可判定语言证明：构造一个判定ANFA的TM N ，用M作为N的子程序，因为M被设计成只接受DFA 作为输入，故N先将作为输入所受到的NFA转换成DFA，然后再将它传给MN=“对于输入,其中B是NFA，w是串：1） 将NFA B 转换成一个等价的DFA C2） 再输入上像上面定理一样运行TM M3） 如果M解说，则接受，否则拒绝”定理：AREX是一个可判定语言(正则表达式是否派生一个给定的串)证明 下面的图灵机判定AREX，P=“在输入上，其中R是正则表达式，w是串：1） 将正则表达式R转换成一个与之等价的NFA A2） 再输入上运行TM N3） 如果N接受，则接受；如果N拒绝，则拒绝“定理：EDFA是一个可判定语言(空性质测试)证明 DFA接受一个串当且仅当：从骑士装他i出发，沿着此DFA的箭头方向，能够到达一个接受状态，为检查这个条件，设计一个使用标记算法的TM TT=“对于输入,其中A是一个DFA:1) 标记A的起始状态2) 重复下列步骤，直到所有状态都被标记3) 对于一个状态，如果有一个到达他的转移是从某个已经标记过的状态出发的，则将其标记4) 如果没有接受状态被标记，则接受，否则拒绝“定理：EQDFA是一个可判定语言(检查两个DFA是否识别同一个语言)证明 下面由A和B来构造一个新的DFA C 使得C只接受这样额串：A或B接受但不是都接 受，这样如果A和B识别相同的语言，则C什么串也不接受，C的语言是L(C)=L（A）交非L(B)并非 L（A）交L(B)，因为正则语言了i再补，并和交下是封闭的，检查L（C）是否为空，如果是空的L(A)和L(B)必定相等F=“对于输入,气宗A和B都是DFA1） 如上面数那样构造DFA C2） 再输入上检查L（C）是否为空3） 如果T接受，则接受；如果T拒绝，则拒绝“定理：ACFG是一个可判定语言证明 识别ACFG的TM S如下：S=“对于输入其中，G是一个CFG，w是一个串1) 将G转换成一个与之等价的乔姆斯基文法2) 列出所有2n-1步的派生其中n是w的长度，除非n=0，此时列出一步以内的派生3) 如果这些派生中有一个产生w，则接受；如果没有，则拒绝“定理：ECFG是一个可判定语言（检查一个CFG是否不派生任何串）证明 R=“对于输入，其中G是一个CFG1）将G中所有的终结符的全都作上标记，重复下列步骤，直到找不到可以做标记的变元2）重复下列步骤，直到找不到可以做标记的变元3）如果G有规则AU1U2Uk，且U1，U2，Uk中的每个符号都已被做过标记，则将变元A做标记4）如果起始状态没有被标记，则接受；否则拒绝“EQCFG是不可判定的定理：每个上下文无关语言都是可判定的证明 设G是A的一个CFG，下面设计一个判定的TM MG他在自己内部建立G的一个备份，其工作方式如下：MG=”对于输入w：1） 再输入上运行TM S2） 如果该机器接受，则接受；否则拒绝”定理 HALTTM是不可判定的（确定一个图灵机对给定的输入是否停机）证明 为了得到矛盾，假设TM R判定HALTTM,由之可以构造TM S来判定ATM,其构造如下：S=“再输入上，此处 是TM M的和串w的编码：1） 在输入 上运行TM R2） 如果R拒绝，则拒绝3） 如果R接受，则在w上模拟M，直到他停机4） 如果M已经接受，则接受；如果M已经拒绝，则拒绝“显然，如果R判定HALTTM，则S判定ATM，因为ATM是不可判定的，故HALTTM也必定是不可判定的定理 ETM是不可判定的(图灵机不接受任何串L(M)=)证明 M1=”再输入x上：1）如果x不等于w，则拒绝2）如果x=w则在x上运行M，当M接受时，就接受”这个机器以w作为他的描述的一部分，检查x=w是否成立的方法很显然，即扫描输入并且一个字符一个字符第将他与w进行比较，就可确定他们是否相同，在假设TM R判定ETM，如下构造判定ATM的TM S：S=“再输入上，此处 是TM M的和串w的编码：1） 用M和w的描述来构造上述TM M12）再输入上运行R3）如果R接受，则拒绝；如果R拒绝，则接受“如果R是ETM的判定其，则S就是ATM的判定其，而后者是不存在的，故我们知道ETM必定是不可判定的定理 REGULARTM是不可判定的（测定一个给定的图灵机是否有一个与之等价的有穷自动机问题）证明 设R是判定REGULARTM的一个TM ,下面构造判定Atm的TM S，S的运行方式如下：S=“对于输入其中M是TM，w是串：1） 构造下述TM M2：M2=”再输入x上：a）如果x具有形式0n1n，则接受b）如果x不具有此形式，则在输入w上运行M，如果M接受w，则接受”2）再输入上运行R3）如果R接受，则接受；如果R拒绝，则拒绝”定理 EQTM是不可判定的证明 设TM R判定EQTM，如下构造判定ETM 的TM S：S=“对于输入,其中M是TM：1）在输入上运行R，其中M1是拒绝所有输入的图灵机2）如果R接受；则接受；如果R拒绝，则拒绝”如果R判定EQTM，则S判定ETM，但ETM是不可判定的，故EQTM也必定是不可判定的定理 如果AmB且B是可判定的，则A也是可判定的证明 设M是B的判定其，f是A都B的归约，A的判定器N的描述如下：N=“对于输入w：1）计算f（w）2）在f（w）上运行M，输出M的输出”显然，如果w属于A则f（w）属于B，因为f是从A到B的归约，因此，只要w属于A，则M接受f(w)，故N的运行正如所求递归定理 设T是计算函数t：*的一个图灵机，则存在计算函数r：*的一个图灵机R，是的对每一个w，有r(w)=t(,w)定理 一个语言在NP中，当且仅当它能被某个非确定型多项式时间图灵机判定证明 对于该定理从左向右的方向，设A属于NP，要证A被多项式时间NTM N判定，由NP的定义，存在A的多项式时间验证机V，假设V是一个在时间nk内运行的TM，构造N如下：N=“对长为n的输入w： 1）非确定地选择最长为nk的字符串c2）再输入上运行V3）若V接受，则接受,否则拒绝”为了证明该定理的另一个方向，假设A呗多项式时间NTM N判定，构造多想时间验证机V如下：V=“对输入,这里w，c是字符串:1)在输入w上模拟N，把c的每一个符号看做是对每一步所做的非确定性选择的描述2）若N的计算分支接受，则接受；否则，拒绝”定理 CLIQUE属于NP证明 下面是CLIQUE的验证机V V=“对输入,c: 1）检查c是否是G中k个结点的集合2）检查G是否包含连接c终结点的所有边3）若两项检查都通过，则接受；否则，拒绝”定义 如果语言B满足下面两个条件，就称为NP完全的：1）B属于NP并且2）NP中的每个A都多项式时间可归约到B定理 若上述的B是NP完全的，且B属于P，则P=NP定理 若上述的B是NP完全的，且B=pC，C属于NP，则C是NP完全的萨维奇定理 对于任何函数f：NR+,其中f(n)=n,NSPACE(f(n)包含于SPACE(f2(n)定义 语言B是PSPACE完全的，若它满足下面两个条件：1）B属于PSPACE2）PSPACE中的每一个语言A多项式时间可归约到B，如果B只满足条件2，则成它为PSPACE难的语言B是NL完全的，如果1）B属于NL，并且2)NL中的每个A对数空间可归约到B定义 函数f：NN,f(n)至少为O(logn)，如果函数f把1n映射为f(n)的二进制表示，并且该函数在空间O(f(n)内是可计算的，称该函数为空间可构造的推论 对于任意两个函数f1，f2:NN,其中f1(n)等于o(f2(n),f2是空间可构造的，有SPACE(f1(n)不包含于SPACE(f2(n)定义 针对一个语言A的谕示是一个能够判断任何串w是否在该语言中的设备，谕示图灵机MA就是给通常的图灵机附加一条带子，称为谕示带，每当MA在谕示带上写下一个字符串时，他就能在一步内计算得知这个字符串是否属于A，令PA是采用谕示A的多项式时间谕示图灵机可判定的语言类，类似地可以定义NPA定义 概率图灵机M是一种非确定型图灵机，它的每一非确定性步，称作掷硬币步，并且有两个合法的下次动作按照下述方式吧概率付给M对输入w的每一个计算分支b，定义分支b的概率为Prb=2-k其中，k是在分支b中出现的掷硬币步的步数，定义M接受w的概率为PrM接受w= Prbb是接受分支定义 BPP是多项式时间的概率图灵机以错误概率1/3识别的语言类费马测试 定理 如果p是素数，且a属于ZP+,则ap-1恒等于1(mod p)定理 泵引理 若A是一个正则语言，则存在一个数p(泵长度)使得，如果s是A中任一长度不小于p的字符串，那么s可以被分成3段，s=xyz，满足下述条件：1）对每一个i=0，xyiz属于A2）|y|0 3）|xy|=p例题 这里展示一个非正则的一元语言，设D=1n的2|n=0，即，D包含所有由1组成、长度为完全平方的字符串，用泵引理证明D不是正则的，证明采用反证法现在考虑两个字符串xyz和xy2z，他们之间相差y的一次反复，因而他们的长度相差y的长度，根据泵引理的条件3，|xy|=p从而|y|=p,由于|xyz|=p2所以xy2z= p2+p但是p2+p p2这样xy2z的长度严格地在p2和(p+1)2这两个连续的完全平方数之间，因此该长度肯定不是一个完全平方数，从而得出结论xy2z不属于D并且D不是正则的定理 一个语言是图灵可是别的，当且仅当存在枚举器枚举它证明 首先证明，如果有枚举器E枚举语言A，则有TM M识别A，TM M如下运行：M=“对于输入w：1）运行E，每当E输出一个串时，将之与w比较2）如果w曾经在E的输出中出现过，则接受“显然，M接受在E的输出序列中出现过的那些串，现在证明另一个方向，设s1，s2，。是*中的所有串，如果TM M识别语言A，为A构造枚举器E如下：E=“忽略输入1）对i=1,2,3.。重复下列步骤2）对s1，s2.。si中的每一个，M以其作为输入运行i步，3）如果有计算接受，则打印出相应的sj，如果M接受串s，它终将出现在打印列表中”有穷自动机和图灵机的区别：1） 图灵机在带子上技能度也能写2）图灵机的读写头既能向左也能向右移动3）图灵机的带子是无限长的4）图灵机进入拒绝和接受状态将立即停机例题 描述TM M，他判定裹的语言是所有由0组成、长度为2的方幂的字符串M=“对于输入字符串w：1）从左往右扫描整个带子，隔一个字符消去一个02）如果在第1步之后，带子上只剩下卫衣的一个0，则接受3）如果在第1步之后，带子上包含不止一个0，并且0的个数是基数，则拒绝4）读写头返回至带子的最左端5）转到第1步”元素区分问题M=”对于输入w：1）在最左端的带符号的顶上做个记号，如果此带符号是空白符，则接受，如果此符号是#，则进行下一步，否则，拒绝2）向右扫描至下一个#，并在其顶上做第二个记号，如果在遇到空白符之前没有遇到#，则带上只有x1，因此接受3）通过来回移动，比较做了记号的#的右边的两个字符串，如果他们相等，则拒绝4）将两个记号中右边的那个向右移到了下一个#上，如果在碰到空白符之前没有遇到#，则将左边的记号向右移到下一个#上，并且将右边记号移到后面的#上，如果这时右边的记号还找不到#，则所有的字符串都已经比较过了，因而接受5）转到第3步继续执行“ALBA是可判定的证明 判定ALBA的算法如下：L=“对于输入，其中M是LBA，w试穿：1）在w上模拟M qngn步，或者知道他停机2）如果M停机，则当他接受时接受，拒绝是拒绝“如果她还没有停机，就拒绝”如果M在w上运行qngn步还没有停机，他必定在重复某个格局，即陷入了循环，这就是算法为什么在此情形下拒绝的原因，LBA和TM有一个本质的不同：对LBA，接收问题是可判定的，但对TM来说却不是，ELBA是不可判定的证明EQCFG是不可判定的。解：只须证明ALLCFGmEQCFG 即可。构造CFG G1，使L(G1)=*。设计从ALLCFG到EQCFG的归约函数如下：F=“对于输入G，其中G是CFG：输出G,G1。”若GALLCFG，则EQCFG 。若GALLCFG，则EQCFG。F将ALLCFG 归约到EQCFG 即ALLCFGmEQCFGALLCFG是不可判定