计算理论习题答案CHAP8new.doc

8.1 证明对于任意函数f:NN，其中f(n)n，不论用单带TM模型还是用两带只读输入TM模型，所定义的空间复杂性类SPACE(f(n)总是相同的。证明：为区别，记单带TM模型在f(n)空间内能判定的语言类为SPACE1(f(n), 而记双带只读输入TM模型在f(n)空间内能判定的语言类为SPACE2(f(n)。该题要证明的是SPACE1(f(n)SPACE2(f(n)。首先SPACE1(f(n)SPACE2(f(n)。这是因为设ASPACE1(f(n)，且设M设在f(n)空间内判定A的单带TM，如下构造双带TM只读输入TM N。N=“对于输入串w：1) 将w复制到工作带上。2) 在工作带上模拟M，直到停机。3) 若M接受，则接受；否则，拒绝。”N在f(n)空间内运行，L(N)=L(M)=A，所以ASPACE2(f(n)。首先SPACE2(f(n)SPACE1(f(n)。设ASPACE2(f(n)，且N为在f(n)空间内判定A的双带只读输入TM。按照用单带TM模拟多带TM的常规方式构造M：M“对于输入串w：1) 初始化工作带为w1w2wn#.其中以标记N的两个读写头。2) 模拟N运行直到停机。每一步模拟，要两次扫描带子。第一次扫描确定读写头下符号，第二次扫描根据N的转移函数完成改写和移动读写头的工作。3) 若N接受，则接受；否则，拒绝。”L(M)=L(N)=A。由于f(n)n，M的运行空间是f(n)+n+2O(f(n)。8.3 考虑广义地理学游戏，其中起始节点就是又无源箭头指入的节点。选手I有必胜策略吗？选手II呢？给出理由。123456IIIIIIIWinner236I456II由表上来看选手II有必胜策略I2II4(不能选3)I5II6(不能选2)I。8.4 证明PSPACE在并、补和星号运算下封闭。证明：(1) 并：对任意 L1, L2PSPACE，设有na空间图灵机M1和nb空间图灵机M2 判定它们，且c=maxa,b。对L1L2 构造判定器M:M=“对于输入字符串w=w1w2wn:1) 初始化将带子改写为w1w1 w2w2wnwn。2) 在w上分别运行M1和M2，即在奇数格运行M1和在偶数格运行M2。3) 若有一个接受则接受，否则拒绝。” 空间复杂度：na+nb=O(nc),所以L1L2属于PSPACE，即 PSPACE在并的运算下封闭。(2) 补：对任意 L1属于PSPACE，设有空间na判定器M1判定它。令L2为L1的补，构造L2的判定器M:M=“对于输入字符串w :1) w上运行M1。2) 若M1接受则拒绝，若M1拒绝则接受。”空间复杂度为：na。所以L2属于PSPACE类，即PSPACE在补的运算下封闭。(3)星号：设M为判定A的空间na图灵机。设计如下TM：D=“对于输入y=y1y2yn:1) 若y=，则接受；2) 对于i,j1,2,n(ij)重复(3)。3) 在yiyi+1yj上运行M。若接受，则令T(i, j)=“yes”。4) 重复下面步骤直到表T不再改变。5) 对于i,j1,2,n(ij)重复下面步骤。 6) 若T(i,j)=“yes”，转(5)。否则继续。7) 对于k=i,j-1,若T(i,k)=T(k+1,j)=“yes”,则令T(i,j)=“yes”.8) 若T(1, n)=yes，则接受；否则拒绝。”运行空间：第3)步模拟M运行需要na空间，存储表T需要n2空间，所以A*属于PSPACE。8.5 证明NL在并、补和星号运算下封闭。证明：(1) 并：对任意 L1, L2NL，设有O(logn)空间图灵机M1和M2 判定它们，且c=maxa,b。对L1L2 构造判定器M:M=“对于输入字符串w=w1w2wn:1) 初始化将带子改写为w1w1 w2w2wnwn。2) 在w上分别运行M1和M2，即在奇数格运行M1和在偶数格运行M2。3) 若有一个接受，则接受；否则拒绝。” 空间复杂度：2O(logn)=O(logn), 所以L1L2属于NL，即 NL在并的运算下封闭。(2) 并：对任意 L1, L2NL，设有O(logn)空间图灵机M1和M2 判定它们，且c=maxa,b。对L1L2 构造判定器M:M=“对于输入字符串w=w1w2wn:1) 初始化将带子改写为w1w1 w2w2wnwn。2) 在w上分别运行M1和M2，即在奇数格运行M1和在偶数格运行M2。3) 若两个都接受，则接受；否则，拒绝。” 空间复杂度：2O(logn)=O(logn), 所以L1L2属于NL，即 NL在交的运算下封闭。(3)星号：设M为判定A的空间O(logn)图灵机。设计如下TM：D=“对于输入y=y1y2yn，1) 令i=1.2) 若in,非确定的选取jn,重复以下步骤。3) 以二进制将i,j存储于工作带。4) 对于yiyi+1yj运行M。5) 若M拒绝，则拒绝；若M接受，则令i=j+1。6) 接受。运行空间：第4)步模拟M运行需要O(logn)空间，存储i,j需要2logn空间，所以A*属于NL。8.6证明PSPACE难的语言也是NP难的。证明:称B是PSPACE难的，若对于任意A属于PSPACE,都有APB。称B是NP难的，若对于任意A属于NP,都有APB。现在设B是PSPACE难的。对于任意A属于NP，由于NPPSPACE，所以APB。这说明B也是NP难的。8.7 证明ADFA属于L。证明：构造如下双带只读输入TM：P=“对于输入,M是DFA，w是串：1) 在w上模拟M运行，每次以二进制记录当前状态编号和当前所读符号个数。2) 若w读完后M接受，则接受；否则，拒绝。”设M的状态数加w长度为n则P需要2logn空间存储当前状态编号，已读符号个数。8.29 证明ANFA是NL完全的。证明：首先证明ANFA属于NL。构造图灵机N=“对于输入,其中M是NFA, w=w1w2wn是串:1) 设置当前状态为起始状态，以二进制记录其编号。2) 对于i=1,2,n,n+1重复以下步骤。3) 非确定的选取0jk，其中k是M的状态数。根据转移函数，由e箭头转移j次，每次非确定的选择下一个状态。4) 若in，根据转移函数，当前状态和wi，非确定的选择下一个状态。5) 若当前状态是接受状态，则接受。”再证明ANFA是NL完全