定理 设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>,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>，x和y是二进制表示的自然数：1）重复下面的操作，知道y=0 2）赋值x←x mod y3）交换x和y的值 4）输出x”算反R以E为子程序求解RELPRIME，R=”对输入<x,y>x和y是二进制表示的自然数： 1）在<x，y>上运行E， 2）若结果为1，就接受；否则，就拒绝”显然，若E在多项式时间内运行且正确，则R也在多项式时间内运行且正确，所以只需分析E的时候和正确性，步骤2的每一次执行（除了第一次有可能例外）都把x的值至少减少一半，执行步骤2以后，由函数mod的性质知x<y步骤3后，有x>y因为这两个值已经交换，于是当步骤2随后执行时有x>y，若x/2>=y,则x mod y<y<=x/2，x至少减少一半，若x/2<y，则x mod y=x-y<x/2,x至少减少一半，每一次执行步骤3都是x和y的值相互交换，所以每两次循环就使得x和y原先的值至少减少一半，于是步骤2和4执行的最大次
数是2log2x和2log2y中较小的那一个，这两个对数宇表示的长度成正比，步骤的执行次数是O(n)，E的每一步消耗多项式时间，所以整个运行时间是多项式的
根号n<n<nloglogn<nlogn<n2<c
正则的<上下文无关的<可判定的<图灵可识别的
定理：ADFA是一个可判定语言
证明：首先检查输入<B,w>，他表示输入串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，然后再将它传给M
N=“对于输入<B,w>,其中B是NFA，w是串：
1） 将NFA B 转换成一个等价的DFA C
2） 再输入<C,w>上像上面定理一样运行TM M
3） 如果M解说，则接受，否则拒绝”
字符串处理函数 如果是a展示b
定理：AREX是一个可判定语言(正则表达式是否派生一个给定的串)
证明 下面的图灵机判定AREX，
    P=“在输入<R,w>上，其中R是正则表达式，w是串：
1） 将正则表达式R转换成一个与之等价的NFA A
2） 再输入<A,w>上运行TM N
3） 如果N接受，则接受；如果N拒绝，则拒绝“
定理：EDFA是一个可判定语言(空性质测试)
证明 DFA接受一个串当且仅当：从骑士装他i出发，沿着此DFA的箭头方向，能够到达一        个接受状态，为检查这个条件，设计一个使用标记算法的TM T
    T=“对于输入<A>,其中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>,气宗A和B都是DFA
1） 如上面数那样构造DFA C
2） 再输入<C>上检查L（C）是否为空
3） 如果T接受，则接受；如果T拒绝，则拒绝“
定理：ACFG是一个可判定语言
证明 识别ACFG的TM S如下：
    S=“对于输入<G,w>其中，G是一个CFG，w是一个串
1) 将G转换成一个与之等价的乔姆斯基文法
2) 列出所有2n-1步的派生其中n是w的长度，除非n=0，此时列出一步以内的派生
3) 如果这些派生中有一个产生w，则接受；如果没有，则拒绝“
定理：ECFG是一个可判定语言（检查一个CFG是否不派生任何串）
证明 R=“对于输入<G>，其中G是一个CFG
    1）将G中所有的终结符的全都作上标记，重复下列步骤，直到不到可以做标记的变元
    2）重复下列步骤，直到不到可以做标记的变元
    3）如果G有规则A→U1U2…Uk，且U1，U2，…Uk中的每个符号都已被做过标记，则将变元A做标记
    4）如果起始状态没有被标记，则接受；否则拒绝“
EQCFG是不可判定的
定理：每个上下文无关语言都是可判定的
证明 设G是A的一个CFG，下面设计一个判定的TM MG他在自己内部建立G的一个备份，其工作方式如下：
    MG=”对于输入w：
1） 再输入<G,w>上运行TM S
2） 如果该机器接受，则接受；否则拒绝”
定理 HALTTM是不可判定的（确定一个图灵机对给定的输入是否停机）
证明 为了得到矛盾，假设TM R判定HALTTM,由之可以构造TM S来判定ATM,其构造如下：
S=“再输入<M,w>上，此处<M,w> 是TM M的和串w的编码：
1） 在输入<M,w> 上运行TM R
2） 如果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=“再输入<M,w>上，此处<M,w> 是TM M的和串w的编码：
1） 用M和w的描述来构造上述TM M12）再输入<M1>上运行R3）如果R接受，则拒绝；如果R拒绝，则接受“如果R是ETM的判定其，则S就是ATM的判定其，而后者是不存在的，故
我们知道ETM必定是不可判定的
定理 REGULARTM是不可判定的（测定一个给定的图灵机是否有一个与之等价的有穷自动机问题）
证明 设R是判定REGULARTM的一个TM ,下面构造判定Atm的TM S，S的运行方式如下：
S=“对于输入<M,w>其中M是TM，w是串：
1） 构造下述TM M2：M2=”再输入x上：a）如果x具有形式0n1n，则接受b）如果x不具有此形式，则在输入w上运行M，如果M接受w，则接受”2）再输入<M2>上运行R3）如果R接受，则接受；如果R拒绝，则拒绝”
定理 EQTM是不可判定的
证明 设TM R判定EQTM，如下构造判定ETM 的TM S：
S=“对于输入<M>,其中M是TM：1）在输入<M,M1>上运行R，其中M1是拒绝所有输入的图灵机2）如果R接受；则接受；如果R拒绝，则拒绝”
如果R判定EQTM，则S判定ETM，但ETM是不可判定的，故EQTM也必定是不可判定的
定理 如果A《mB且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(<R>,w)
定理 一个语言在NP中，当且仅当它能被某个非确定型多项式时间图灵机判定
证明 对于该定理从左向右的方向，设A属于NP，要证A被多项式时间NTM N判定，由NP的定义，存在A的多项式时间验证机V，假设V是一个在时间nk内运行的TM，构造N如下：N=“对长为n的输入w： 1）非确定地选择最长为nk的字符串c2）再输入<w,c>上运行V3）若V接受，则接受,否则拒绝”为了证明该定理的另一个方向，假设A呗多项式时间NTM N判定，
构造多想时间验证机V如下：V=“对输入<w,c>,这里w，c是字符串:1)在输入w上模拟N，把c的每一个符号看做是对每一步所做的非确定性选择的描述2）若N的计算分支接受，则接受；否则，拒绝”
定理 CLIQUE属于NP
证明 下面是CLIQUE的验证机V  V=“对输入<<G,k>,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：N→R+,其中f(n)>=n,NSPACE(f(n))包含于SPACE(f2(n))

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。