tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 数学 >>

定理证明例题


定理 设 t(n)是一个函数,t(n)>=n,则每一个 t(n)时间的多带图灵机都和某一个 O(t2(n))时间的单带图灵机等价 设 t(n)是一个函数,t(n)>=n,则每一个 t(n)时间的非确定型单带图灵机都与某一个 2 O(t(n))时间的确定型单带图灵机等价 定义 P 是确定型单带图灵机在在多项式时间内可判定的语言类,换言之: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 解说,则接受,否则拒绝” 定理: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) 2) 3) 标记 A 的起始状态 重复下列步骤,直到所有状态都被标记 对于一个状态,如果有一个到达他的转移是从某个已经标记过的状态出发的,则将其标记 个接受状态, 为检查这个条 作为输 1TIME )对于所有与确定型单带图灵 (n ) ?
k k

机多项式的等价的计算模型来说,P 是不变的 2)P 大致对应于在计算机上时即可解的那一类问题

4)

如果没有接受状态被标记,则接受,否则拒绝“ 受,这样如果 A 和 B

定理:EQDFA 是一个可判定语言(检查两个 DFA 是否识别同一个语言) 证明 下面由 A 和 B 来构造一个新的 DFA C 使得 C 只接受这样额串:A 或 B 接受但不是都接 识别相同的语言,则 C 什么串也不接受,C 的语言是 L(C)=L(A) 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) 2) 3) 将 G 转换成一个与之等价的乔姆斯基文法 列出所有 2n-1 步的派生其中 n 是 w 的长度,除非 n=0,此时列出一步以内的派生 如果这些派生中有一个产生 w,则接受;如果没有,则拒绝“ i 再补,并和交下是封闭的,检查 L(C) 是否为空,如果是空的 L(A)和 L(B)必定相等 交非 L(B)并非 L(A)交 L(B),因为正则语言了

定理: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)) 定义 语言 B 是 PSPACE 完全的,若它满足下面两个条件:1)B 属于 PSPACE2)PSPACE 中的每一个语言 A 多项式时间可 归约到 B,如果 B 只满足条件 2,则成它为 PSPACE 难的 语言 B 是 NL 完全的,如果 1)B 属于 NL,并且 2)NL 中的每个 A 对数空间可归约到 B 定义 函数 f:N→N,f(n)至少为 O(logn),如果函数 f 把 1 映射为 f(n)的二进制表示,并且该函数在空间 O(f(n))内是可计 算的,称该函数为空间可构造的 推论 对于任意两个函数 f1, f2:N→N,其中 f1(n)等于 o(f2(n)),f2 是空间可构造的, 有 SPACE(f1(n))不包含于 SPACE(f2(n)) 定义 针对一个语言 A 的谕示是一个能够判断任何串 w 是否在该语言中的设备,谕示图灵机 M 就是给通常的图灵机附加一条 带子,称为谕示带,每当 M 在谕示带上写下一个字符串时,他就能在一步内计算得知这个字符串是否属于 A,令 P 是采用谕 示 A 的多项式时间谕示图灵机可判定的语言类,类似地可以定义 NP
A A A A n

定义 概率图灵机 M 是一种非确定型图灵机,它的每一非确定性步,称作掷硬币步,并且有两个合法的下次动作按照下述方 式吧概率付给 M 对输入 w 的每一个计算分支 b, 定义分支 b 的概率为 Pr[b]=2 其中, k 是在分支 b 中出现的掷硬币步的步数, 定义 M 接受 w 的概率为 Pr[M 接受 w]= ∑Pr[b]b 是接受分支 定义 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 理证明 D 不是正则的,证明采用反证法 现在考虑两个字符串 xyz 和 xy2z, 他们之间相差 y 的一次反复, 因而他们的长度相差 y 的长度, 根据泵引理的条件 3, |xy|<=p 从而|y|<=p,由于|xyz|=p2 所以 xy2z<= p2+p 但是 p2+p< p2+2p+1=(p+1)2,此外条件 2 意味 y 不是空串, 所以|xy2z|> 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,它终将出现在打印列表中”
的2 -k

|n}=0},即,D 包含所有由 1 组成、长度为完全平方的字符串,用泵引

有穷自动机和图灵机的区别: 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,w>,其中 M 是 LBA,w 试穿:1)在 w 上模拟 M qngn 步,或者知道他停机 2)如果 M 停机,则当他接受时接受,拒绝是拒绝“如果她还没有停机,就拒绝”如果 M 在 w 上运行 qngn 步还没有停机, 他必定在重复某个格局,即陷入了循环,这就是算法为什么在此情形下拒绝的原因, LBA 和 TM 有一个本质的不同:对 LBA,接收问题是可判定的,但对 TM 来说却不是,ELBA 是不可判定的

证明 EQCFG 是不可判定的。
解:只须证明 ALLCFG≤mEQCFG 即可。构造 CFG G1,使 L(G1)=∑*。设计从 ALLCFG 到 EQCFG 的归约函数如下: F= “ 对 于 输入<G>,其中 G 是 CFG:输出<G,G1>。 ” 若<G>?ALLCFG, 则<G,G1>?EQCFG 。 若<G>?ALLCFG, 则<G, G1>?EQCFG。 F 将 ALLCFG 归约到 EQCFG 即 ALLCFG≤mEQCFG∵ALLCFG 是不可判定的,∴EQCFG 是不可判定的。 复杂性理论与可计算性理论之间的一个重大区别:在可计算性理论中,所有合理的计算模型都是等价的,即他们所判定的 语言类都是相同的,在复杂性理论中,模型的选择影响语言的时间复杂度 当分析一个算法,证明他在多项式时间内运行时,需要做两件事,首先,必须为算法在长为 n 的输入上运行时所需要的步 骤数给出多项式上界(一般用大 O 记法) ,其次必须考察算法描述中的每一步,保证他们都可以由合理的确定型模型在多项 式时间内实现,在描述算法时,仔细确定他的步骤,以使第二部分分析容易进行,当两部分年工作都完成以后,就可以下结 论:算反在多项式时间内运行 P 与 NP 的区别:P/NP=成员资格可以快速地判定/验证的语言类 PRIME 算法 PRIME=”对于输入 p:1)如果 p 是偶数,则如果 p=2,则接受;否则拒绝 2)在 Zp+中随机的选取 a1...ak3)对 i=1, 。 。 。k4)计算 aip-1 mod p,并且如果不等于 1,则拒绝 5)令 p-1=st,其中 s 是奇数,t=2h 是 2 的幂 6)计算序列 ais*2
幂 的0 次

,ais*2

的 1 次幂

, 。 。 。ais*2

的 k 次幂

mod p7)如果该序列中的某个数不等于 1,则找到最后一个不等于 1 的数,如果这书不等于-1,

则拒绝 8)这时已经通过全部测试,故接受” 天窗函数:3 个条件 1)函数 f 和 h 是多项式时间可计算的 2)对于每一个多项式时间概率图灵机 E、每一个 k 和充分大的 n, 如果取 G 对 1n 的随机输出<i,t>和随机串 w 属于∑n,则 PrM,w[E(i,fi(w))=y,其中 fi(y)= fi(w)]<=n-k 3)对于每一个 n。每一个长度 n 的 w 和 G 对任意输入以非零概率输出的每一个<i,t>,有 h(t, fi(w))=y,这里 fi(y)= fi(w)


推荐相关:

微分中值定理的证明题[1](1)

微分中值定理证明题[1](1)_数学_自然科学_专业资料。微分中值定理证明题 1. 若 f ( x) 在 [a, b] 上连续,在 ( a, b) 上可导, f (a) ?...


中值定理证明题

中值定理证明题。中值定理证明5、 验证罗尔定理对f ( x ) = 3 x + 3 1 ? x 在[0,1]上的正确性 6、 验证罗尔定理对f ( x ) = x 3 + 5x ...


定理证明例题

(n))时间的确定型单带图灵机等价 定义 P 是确定型单带图灵机在在多项式时间内可判定的语言类,换言之:P= 定理 PATH 属于 P 证明 PATH 的一个多项式时间算法...


有关中值定理的证明题

有关中值定理的证明题_理学_高等教育_教育专区。中值定理证明题集锦 1、已知函数 f ( x) 具有二阶导数,且 lim x ?0 f ( x) ? 0 , f (1) ? 0 ...


勾股定理解答证明题

勾股定理解答证明题_初二数学_数学_初中教育_教育专区。人教版初二数学勾股定理训练题《勾股定理》证明解答题练习 1、在 ?ABC 中, AB ? AC , D 为 BC 边上...


微分中值定理的证明题

f (? ) . 【分析】 f (x) 在[0,2a]上连续,条件中没有涉及导数或微分,用介值定理或根的 存在性定理证明。辅助函数可如下得到 f (a ? ? ) ? f (...


中值定理证明题练习

中值定理证明题练习_研究生入学考试_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档中值定理证明题练习_研究生入学考试_高等教育_教育专区。1、设 f ( ...


微分中值定理证明题中构造函数的逆推方法

大家在做微分中值定理证明题的时候常常会好奇它的 构造函数是怎么推出来的,我在这里传授一下存在在微分中 值定理证明题中是怎么推出构造函数的。 先看这一题,已...


与微分中值定理有关的证明题

与微分中值定理有关的证明题一.利用罗尔定理 1. f ( x ) 在[0 ,1]上有二阶导数,且 f (1) = 0 ,又 F ( x) = x f ( x) , 求证:在(0 ,...


2016年考研数学中值定理证明题技巧 以及结论汇总

2016年考研数学中值定理证明题技巧 以及结论汇总_研究生入学考试_高等教育_教育专区。2016年考研数学中值定理证明题技巧 以及结论汇总2016年考研数学中值定理证明题...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com