2025年计算理论真题及答案研究生部分答案已参考老师的答案还有我们做的本科生部分的答案VIP专享

这是我们（32 舍 388）参照老师的课堂内容整理的的答案，附带解析。由于时间仓促，错误必然不少，请各位见谅并吐槽指正。G 版(a) F 不一定。由于假设 A 是{Σ*}，B 是{M 在“M”上不停机}，符合题目规定，B 不是可判定的。(b) T 假如 A 可以归约到 B，根据归约的定义，x∈A 的时候 t(x)∈B，反之，x∉A，即 x∈A的补的时候 t(x)∉B，即 t(x)∈B 的补。(c) F 由于 DFA 总有停机的时候，对于一种 DFA 输入“M”，这个 DFA 总会读完所有的字符然后给出 yes 或者 no，因此这个语言是递归的。老师课堂上说 DDFA是非正则的，这是可以用对角化定理证明 DDFA和每个正则语言都不一样样，证明和书本 165 页中间的相似。(d) T 这个非递归可枚举的语言就是书本 164 下面那个 H1 的补，{M 在“M”上不停机}(e) T He 可以用通用图灵机半判定，不过无法判定。停机问题，即图灵机 M 在某个输入 w上与否停机，无法判定，这里让 w=e 即可。(f) F 根据定理 5.4.1，由于 H 不是递归的，因此 L 也不递归了。由于 H≤L 补，因此 H 补≤L。假如 L 是递归可枚举的，那么 H 补也是递归可枚举，那么 H 就不是递归可枚举的了，这和 H 自身是递归可枚举的事实是相悖的，因此 L 不是递归可枚举的。(g) T 假设 M1 半判定 A，M2 半判定 B，M3 半判定 A∪B 的补。对于输入 w，交给M1、M2 和 M3 一起做。假如 M1 接受，那么 w∈A，M2 接受，那么 w∈B，假如 M3 接受，那么 w∉(A∪B)，即不是 A 也不是 B。由于 A 和 B 是不相交的，因此 M1、M2 和 M3 的合体可以判定 A 或者 B，因此 A 和 B 都是可判定的，递归的。(h) T 背面的是 NTIME，应当是不确定性计算的所需时间。因此，我们把 nk看作一体的，称为 a，那么确定计算时间是指数 ca，非确定计算只要 a，也就是 nk了。(i) T B 是 P，A 可以多项式时间归约到 B，因此 A 也是 P，P 对补封闭，因此命题对的。(j) F 假设 A 是这样一种问题，给定一种整数集合和整数 k，求与否存在 k 个元素和不小于C。直观看我们可以用随机抽取 k 个元素然后算和然后假如其中一次不小于 C 就接受。不过我们也可以通过，例如多项式时间的冒泡排序，把集合的整数降序排序，归约到问题B，前 k 个元素的和与否不小于 C，显然 B 是 P 的。因此，只能说假如 B 是 NP 的，A 可以归约到 B，那么 ...