麻省理工学院试卷习题 2005 期末考试_Automata, Computability, and Complexity（自动化、可计算性与复杂性）.pdf_大学文库

6.045J/18.400J: Automata, Computability and Complexity Prof. Nancy Lynch 期末考试 (5.20 2005) 请在每一页的上面写上自己的名字. 问题 1：多项选择题（每题 5 分，共 50 分）：下面每一个选项都可能是正确的。 1、下面关于正则语言和非正则语言的说法哪些是正确的： (A) 如果 L1 是 L2 的一个子集，而 L2 是正则的，那么 L1 肯定也是正则的。 (B) 如果 L1 和 L2 都是非正则的语言，那么 L1∪L2 肯定也是非正则的。 (C) 如果 L1 是非正则的，那么 L1 的补也是非正则的。 (D) 如果 L1 是正则语言， L2 是非正则的语言，并且 L1∩L2 是非正则的，那么 L1∪L2 肯定也是非正则的。 (E) 如果 L1 是正则语言， L2 是非正则的语言，并且 L1∩L2 是正则的，那么 L1∪L2 肯定也是非正则的。 2、下面哪些肯定是正则语言： (A) L2={ww：w∈{0,1}*} (B) L2={ww：w∈L1}，其中 L1 是一个正则语言 (C) L2={w：ww∈L1}，其中 L1 是一个正则语言 (D) L2={w：存在一个 x，使得|w|= |x| 并且 wx∈L1}，其中 L1 是一个正则语言 (E) L2={w：w∈L1，并且 w 的前缀(proper prefix)都不在 L1 中}，其中 L1 是一个正则语言 3、下面哪些说法是正确的： (A) 如果一个语言能被一个 NFA 识别，它肯定能被一个 DFA 识别。 (B) 如果一个语言能被一个非确定型图灵机识别，它肯定能被一个确定型图灵机识别。 (C) 如果一个语言能被一个非确定型图灵机判定，它肯定能被一个确定型图灵机判定。 (D) 如果一个语言能被一个非确定型图灵机在多项式时间内判定，它肯定能被一个确定型图灵机在多项式时间内判定。 (E) 如果一个语言能被一个非确定型图灵机在对数空间内判定，它肯定能被一个确定型图灵机在对数空间内判定。 4、下面哪些语言是不可判定的。 (A)CLIQUE (B){|M 是一个图灵机，L(M)= CLIQUE} (C){|M 是识别一个非空语言的图灵机} (D){|M 是识别一个 NP-难语言的图灵机} (E){|M 是识别语言 L 图灵机，并且 L 能够被另一个拥有偶数个状态的图灵机 M’识别} 5、下列关于图灵机可识别语言的说法哪些是正确的 (A) 如果 L1 是 L2 都是图灵机可识别语言，那么它们的交集和并集都是图灵机可识别的。 (B) 存在这样的语言 L，满足 L 和它的补都不是图灵机可识别的。 (C) 如果 L 是一个图灵机可识别但不是可判定的语言，那么任何识别 L 的图灵机必然会在无穷多的输入上永远的循环。 (D) 如果L1 是L2 都是非平凡语言，而L1 是图灵机可识别的，L2 是可判定的，那么L1∪L2 ≤mL1。 (E) 如果对于所有的i≥1，Li都是图灵可识别的，那么对于i从 1 到无穷大，所以Li的并集组成的语言也是图灵机可识别的。 6、下面所示的构造使用递归定理以及一个假设存在的图灵机判定语言 L 的判定器 D，来构造一个新的图灵机 R： R：在输入 x：

得到，在 D 上运行。如果 D 接受那么拒绝，否则接受。这个构造产生了关于图灵机方面的一些不可判定的语言，下面哪些是的： (A)L={|M 是接受所有的字符串图灵机} (B)L={|M 是接受一些字符串的图灵机} (C)L={|M 是一个图灵机，且接受字符串 00} (D)L={|M 是一个图灵机，且不接受字符串 11} (E)L={| M 是一个图灵机，且接受字符串 00 但不接受字符串 11} 7、下面哪些是已知正确的： (A)3SAT≤P2SAT (B)2SAT≤P3SAT (C) PCP≤PUNDIRECTED-HAMILTONIAN-CIRCUIT (D) VERTEX-COVER≤PUNDIRECTED-HAMILTONIAN-CIRCUIT (E) TQBF≤PPATH∪UNDIRECTED-HAMILTONIAN-CIRCUIT 8、下面关于空间有界复杂度的说法哪些已知是正确的： (A)现在已经知道，TOTNFA，即非确定有限自动状态机的完整性问题，是在PSPACE中 (B)由萨维奇定理可以推出 NSPACE(square_root(log n))是 SPACE(log n)的一个子集 (square_root(a)表示 a 的平方根) (C) TQBF 是一个 NL 完全问题 (D) PATH 在 L 类中 (E) TQBF≤LVERTEX-COVER 9、下列关于 NL=coNL 的证明(证明在 Sipser 书上的 8.6 节)的说法哪些是已知正确的： (A)在非确定性算法的每一个分枝上，每一个变量 ci 被设置为在 G 中从 s 出发经过 i 步并且步长最多为 i 所能到达的结点的数目。 (B) 在算法的每一个分枝上，每一个变量ci被设置为在G中从s出发经过i步并且步长最多为i 所能到达的结点的数目。 (C)当算法到达第二步阶段(书上 328 页上的代码的第 12 行开始)，cm的值可定等于G中从s出发所能到达的结点的数目(这里不限定步长)。 (D)如果我们把 14 行删掉，这会使得算法不确定的跳过一些步骤。即使这样算法仍然能够正确运行，只是要完成的话，时间要长一些。 (E)本构造方式能够比较容易的调整来证明 NP=coNP。 10、下面关于素数测试问题哪些说法是正确的： (A)PRIMES∈BPP。 (B)COMPOSITES∈RP。 (C) PRIMES∈P。 (D)费马小定理所有的合数都不能通过费马测试。即，不存在这样的a∈{1,...,c-1}，满足a c-1≡ 1(mod c)。 (E)每一个非卡米切尔合数在至少一半以上的底数 a 上不能通过费马测试。问题 2：指出错误（20 分） 1、泵引理(10 分)下面的这个“证明”，试图运用泵引理来证明长度为 100 的任意 0 和 1 组成的字符串的语言不是正则的。很明显由于所有的有限长的语言都是正则，所以该“证明”是错误的，请指出其中的错误

为了得到L是正则语言的一个矛盾。我们使用泵引理，我们选择一个L语言的元素，假设为 w=0100，那么有字符串x，y，和z，满足|y|>0，并且所有满足形如xy k z(k≥0)的字符串都在L 中。这样就有很多无限长的字符串会在L中，这与L是有限的相矛盾。因此，L不是正则的。 2、 ≠-SAT 问题的 NP 完全性(10 分) 假设φ使一个 cnf 公式(合取范式公式)，一个对φ变量的≠-赋值是使得每个合取子句中都有两个真值不同的文字量(一个命题变元和它的否都是文字量)，换句话说，一个≠-赋值可以不用对所有的子句中的文字量进行赋值就能满足φ为真。我们定义≠-SAT 问题如下： {φ| φ是一个 cnf 公式，而且存在一个≠-赋值满足φ} 举个例子，就有一个满足的≠- 赋值：x1=true，x2=false，x3=false。 Sally 是本课程一个学生，她知道≠-SAT 是一个 NP 完全问题。为了让另外一个人 Harry 相信她确实是对的，她给出下面从 CNF-SAT 到≠-SAT 的一个规约： “给出一个由k个子句C1，C2,…,Ck公式φ,按照如下的公式来计算公式f(φ)：引入一个新的变量x，并且让子句Ci ’ =Ci∧x。公式f(φ)是所有子句Ci ’ 的合取。” Sally 断言说存在一个合法的从 CNF-SAT 到≠-SAT 的规约，这个规约就能说明≠-SAT 是一个 NP 难的问题。而 Harry 认为 Sally 是不对的，因为他注意到公式 f(φ)中只要简单的把 x 设为 true 就能满足。他们到底谁是对的呢？为什么？问题 3：42 最小机器（15 分）一个图灵机 M 如果满足下列性质：任何和 M 识别相同的语言的图灵机 M’，M’不存在一个小于 M 的 1/42 大小的表示，即 M’的表示至少是 M 的表示的 1/42 那么大。我们就称 M 是 42 最小机器。 1、给定一个图灵机的表示，M 是不是 42 最小机器的问题是可判定的吗？ 2、如果你上小题的答案是肯定的，请给出一个判定的算法，如果你的答案是否定的，请给出证明不存在这样的算法。问题 4：背包问题（25 分）Harry 是一个高年级大学生，他准备暑假去亚马孙丛林去旅行。为了这次旅行，他要给自己打一个背包。他发现自己只能背 42 磅重的东西，但是要带的东西又很多，有杀虫剂，发胶，iPod 播放器，衣物，当地方言的词典，他的玩具熊等等，这些东西总的重量远重于 42 磅。他正在为带什么东西而发愁呢。由于他学习过算法设计的课程，因此他决定给出一个解决本问题的通用算法来。首先作了如下的形式化：用一个所有的项组成的集合 I，每一个项的重量为 w(i),其价值是 v(i)。问题变成了给定一个集合 I，以及一个最大的重量 M，怎样使得在重量最大为 M 的前提下满足价值最大。 1、形式化 Harry 的最优化问题 2、定义语言 BACKPACK，其表示在一个给定的重量之下，一个给定的价值能不能满足 3、证明上述问题是一个 NP 完全问题 4、如果 Harry 能够以零代价来查询 BACKPACK 问题的谕示，那么他怎样能够在多项式时间内来解决他的最优化问题。问题 5：广义棋局（15 分）一个 n*n 的棋盘(n 为偶数)，定义 Generalized-Checkers 为那些在任意的满足条件的 n 值的棋盘上先手能够取胜的格局的集合。更准确的说，我们定义的是 n*n 棋盘上的满足各棋子不能重叠，棋盘的红色部分最多有 (n/2-1)*n/2 个红棋子，(n/2-1)*n/2 个黑棋子的情况下棋盘上的一个棋盘格局。还有一个附加条件就是可以指定任意数量的棋子为王。我们假设先手执黑，他的家在棋盘的顶部。其他的规则就是普通的规则，我们定义 Generalized-Checkers 为下列语言 {|P 是 n*n 棋盘的一个格局，在该格局下先手有必胜的策略} 1、给出一个多项式空间算法来判定语言 Generalized-Checkers

麻省理工学院 试卷习题 2005 期末考试_Automata, Computability, and Complexity（自动化、可计算性与复杂性）

麻省理工学院试卷习题 2005 期末考试_Automata, Computability, and Complexity（自动化、可计算性与复杂性）