计算理论习题答案CHAP7new

7.3a.OperationXY127410505XmodYX127410505XY105051274XmodYX3131274XY1274313XmodYX22313XY31322XmodYX522XY225XmodYX25XY52XmodYX12XY21XmodYX01XY10当Y=0时，输出X=1，所以1274和10505是互素的。7.4对于字符串w=baba和下面的文法CFGG，试填写定理8.14中识别上下文无关语言的多项式时间算法中所描述的表。SRTRTR|aTRT|b解：TR,TSR,T,SRSSTR,TR7.5下面的公式是可满足得吗？=(xy)(xy)(xy)(xy)解:(x,y)共有四种取值：(true,true),(true,false),(false,true),(false,false).分别将其带入公式得：若(x,y)=(true,true)，=(truetrue)(truefalse)(falsetrue)(falsefalse)=false若(x,y)=(true,false)，=(truefalse)(truetrue)(falsefalse)(falsetrue)=false若(x,y)=(false,true)，=(falsetrue)(falsefalse)(truetrue)(truefalse)=false若(x,y)=(false,false),=(falsefalse)(falsetrue)(truefalse)(truetrue)=false所以原公式不可满足。7.6证明P在并、连接和补运算下封闭。(1)并：对任意L1,L2P，设有na时间图灵机M1和nb时间图灵机M2判定它们，且c=max{a,b}。对L1L2构造判定器M:M=“对于输入字符串w:1)在w上运行M1，在w上运行M2。2)若有一个接受则接受，否则拒绝。”时间复杂度：设M1为O(na),M2为O(nb)。令c=max{a,b}。第一步用时O(na+nb)，因此总时间为O(na+nb)=O(nc),所以L1L2属于P类，即P在并的运算下封闭。(2)连接：对任意L1,L2属于P类，设有na时间图灵机M1和nb时间图灵机M2判定它们，且c=max{a,b}。对L1L2构造判定器M:M=“对于输入字符串w=w1,w2,…,wn，1)对k=0,1,2,…,n重复下列步骤。2)在w1w2…wk上运行M1，在wk+1wk+2…wn上运行M2。3)若都接受，则接受。否则继续。4)若对所有分法都不接受则拒绝。“时间复杂度：(n+1)×(O(na)+O(nb))=O(na+1)+O(nb+1)=O(nc+1)，所以L1L2属于P类，即P在连接的运算下封闭。(3)补：对任意L1属于P类，设有时间O(na)判定器M1判定它，对1L构造判定器M:M=“对于输入字符串w:(1)在w上运行M1。(2)若M1接受则拒绝，若M1拒绝则接受。”时间复杂度为：O(na)。所以1L属于P类，即P在补的运算下封闭。7.7证明NP在并和连接运算下封闭。(1)并：对任意L1,L2NP，设分别有na时间非确定图灵机M1和nb时间非确定图灵机M2判定它们，且c=max{a,b}。构造判定L1L2的非确定图灵机M:M=“对于输入字符串w:1)在w上运行M1，在w上运行M2。2)若有一个接受则接受，否则拒绝。”对于每一个非确定计算分支，第一步用时为O(na)+O(nb)，因此总时间为O(na+nb)=O(nc)。所以L1L2NP，即NP在并的运算下封闭。(2)连接：对任意L1,L2NP，设分别有na时间非确定图灵机M1和nb时间非确定图灵机M2判定它们，且c=max{a,b}。构造判定L1L2的非确定图灵机M:M=“对于输入字符串w:1)非确定地将分成两段x,y，使得w=xy。2)在x上运行M1，在y上运行M2。3)若都接受则接受，否则拒绝。”对于每一个非确定计算分支，第一步用时O(n),第二步用时为O(na)+O(nb)，因此总时间为O(na+nb)=O(nc)。所以L1L2NP，即NP在连接运算下封闭。8.8证明如果对数采用一进制编码而不是二进制编码,则素数判定是多项式时间可解的.换句话说,证明语言UNARY-PRIME={1n|n是素数}属于P.证明:设x为被判定的数.构造判定器M.M=“输入1n，n为正整数,1)对k=2,3,…,n-1重复下列步骤。2)对于1n，每次消去k个1。若刚好可以消完，则拒绝。3)若都不能刚好消完，则接受。”时间分析:1)最多执行n-2次,每次1步;2)对于每个k的值,执行步数小于n;3)需要一步整个判定过程需要时间小于(n-2)(1+n)=n2-n-2。运行时间为O(n2)。所以UNARY-PRIMEP。7.8令CONNECTED＝｛G|G是连通的无向图｝。分析4.3.2节给出的算法，证明此语言属于P。证明：判定CONNECTED的TMM的一个高水平描述：M=“输入是图G的编码G：1)选择G的第一个顶点，并作标记。2)重复步骤(3)，直到没有新的顶点可以作标记。3)对于G的每一个顶点，如果存在一条边，将其连到一个已作标记的顶点，则标记该顶点。4)扫描G的所有顶点，确定它们是否都已作了标记，如果是，则接受，否则拒绝。”分析该算法的执行，步骤1)执行一次。一个n个顶点连通的无向图最多有n(n-1)/2条边，所以每次执行步骤3，运行时间是O(n2)。为标记所有的n个顶点，步骤3至多需要执行n次。所以用于标记的总的运行时间是O(n3)。步骤4需要执行n步。该算法的总步数1+O(n3)+n即为O(n3),从而有该语言属于P。7.9无向图中的三角形是一个3-团。证明TRIANGLEP。其中TRIANGLE＝{G|G包含3-团}证明思路：采用相邻矩阵的形式存储图，有n个结点的无向图G存储在矩阵Rn×n中，并且满足：R[i,i]=0,R[i,j]=1(当结点i和结点j之间有一条边)，R[i,j]=∞(当结点i和结点j之间不存在边)。从矩阵的第一行开始逐行扫描矩阵各行，在每一行中找两个为1的元素，假设当前扫描到第i行,若R[i,j]=1且R[i,k]=1，则检查矩阵中R[j,k]是否为1，若成立则接受，否则继续搜索。证明：以算法D实现这一思路。D=“对输入R1）计算R的结点数n。若n≤2，则拒绝。否则转2）2）Fori=1ton3）Forj=i+1ton4）若R[i,j]=1则5）Fork=j+1ton6）若R[i,k]=1则检查矩阵中R[j,k]是否为1，若是则接受7）若i,j,k同时为n，则拒绝。”分析D，每一步都是在多项式时间内运行，步骤2最多运行n次，步骤2每运行一次步骤3最多运行n-i次,步骤3每运行一次步骤4最多运行n-j次。所以总计D执行O(n3)步。7.11证明：构造NTM如下：N=“对于输入G，H，1)比较G与H节点数，若不相同，则拒绝。2)非确定地对G的节点进行重排。3)若G和H完全相同，则接受。否则拒绝”N有n！个计算分支，每个长度为n，则此NTM有多项式时间，所以ISO∈NP。7.12证明MODEXPP。设二进制整数b=kmkm-1…k1k0，则b=k020+k121+k222+…+km2m(ki=0,1)。构造判定MODEXP的图灵机如下：M=“对于输入a,b,c,p，a,b,c,p为二进制整数，(1)以k0,k1,…,kn记b的从低位到高位的1至n+1位。(2)令d0=a，对于i=1,2,…,n计算di=di-1×di-1modp。(3)对于i=0,1,…,n，若ki=1，则令ci=di；若ki=0，则令ci=1。(4)计算e=c0×c1×…×cnmodp。(5)若e=cmodp，则接受，否则拒绝。”设对于两个n位二进制整数，相乘再模一个至多n位的二进制整数，需要运行的时间为T。则第二步的时间为nT，第四步为nT，所以总的运行时间为O(nT)。这意味着MODEXP∈P。7.14证明P在星号运算下封闭。证明：设M为判定A的时间f(n)图灵机，不妨设f(n)n。设计如下TM：D=“对于输入y=y1y2…yn，1)若y=ε，则接受；2)对于i,j＝1,2,…,n重复(3)。3)在yiyi+1…yj上运行M。若接受，则令T(i,j)=“yes”。4)重复下面步骤直到表T不再改变。5)对于i,j＝1,2,…,n重复下面步骤。6)若T(i,j)=“yes”，转(5)。否则继续。7)对于k=i,i+1,…,j-1,若T(i,k)=T(k+1,j)=“yes”,则令T(i,j)=“yes”。8)若T(1,n)=yes，则接受；否则拒绝。运行时间：设O(n2f(n))+O(n3)＝O(n2f(n))。7.15证明NP在星号运算下封闭。证明：设M为判定A的时间f(n)非确定图灵机，不妨设f(n)n。设计如下NTM：D=“对于输入y=y1y2…yn，1)若y=ε，则接受；2)非确定地选择y的一个划分y=x1x2…xk，其中是x1,x2,…,xk字符串。3)对于i=1,2,…,k，重复下一步骤：4)在xi上运行M，若M拒绝，则拒绝。5)若都接受，则接受。”以下略。若有兴趣讨论，可与刘庆晖([e-mail])联系。