Graduate Computational Complexity Theory (CMU 15-855*, Fall 2017)

课程链接: https://www.cs.cmu.edu/~odonnell/complexity17/

Homework 1

1. (Valiant’s Depth-Reduction Lemma.)

a

(1) 如果只有最多 d 个 label, 则最长路径长度为 $d - 1$, 显然小于 d.

(2) 由于图 G 中存在多个源点, 故构造一个虚拟的超源点 s, 从 s 向 G 中每个入度为 0 的点连有向边. 定义 $d(x)$ 为 s 到 x 的最长路径长度, 其中 $d(x)$ 的求解方法类似于关键路径(AOV). 令 $l(x) = d(x)$, 则满足所有节点的直接和间接前驱的 label 都小于自身的 label, 且所有的 label 最多只有 d 个.

b

对于 G 中的每条边 $(u_i, v_i)$, 如果 $(u_i, v_i) \in E_j$, 则这条边会被删去.

如果 $(u_i, v_i) \notin E_j$, 设 $u_i$ 和 $u_v$ 的二进制表示在第 k 位不相同. 如果 $k < j$, 则该删去第 j 位的操作不会改变其大小关系; 否则, 由于 $u_i < v_i$, 所以在第 k 位上, $u_i$取值为 0, $v _i$ 为 1. 删去第 j 位后, 最高的不相同位仍然是第 k 位, 仍然满足 $u _i < v_i$.

综上, 该操作不会破坏 “labeling” 合法性.

c

对于图 G, 其中的所有 m 条边都被划分在 $E_0, E_1, ..., E_{k - 1}$ 中, 满足 $|E_0| + |E_1| + ... + |E_{k - 1}| = m$, 对于任意的 $E_i(0 \leq i < k)$, 满足 $0 \leq E_i \leq m$.

将上述的 k 个边集按照集合的大小从小到大排序, 并按照新的顺序重新依次编号, 得到 $E_0', E_1', ..., E_{k - 1}'$. 记函数 $f(x)$ 为新序号到旧序号的映射. 例如,若原来的 $E_2$ 成为了现在的 $E_0'$, 则有 $f(0) = 2$.

流程如下:

1. 设置一个计数器 count, 初始化为 $count := 0$, 然后执行 2.
2. 如果当前没有边集, 则说明所有的边都已经被删除完毕, 结束. 否则执行 3.
3. 如果当前的第一个边集没有边, 则删除这个边集, 转到 2. 否则执行 4.
4. 如果满足 $count = r/k*m$, 然后执行 5. 否则从当前的第一个边集中删除任意一条边, 然后 $count := count + 1$, 并执行 3.
5. 将所有节点的 label 的二进制表示删去第 $f(0), f(1), ..., f(r - 1)$ 位.

最终得到的图中, 最长路径小于 $d/2^r$.

这个题目的 c 小问假如单独出成一个题目, 便是当初研究这个问题的前辈所面临的考验, 可见这需要相当程度创造性思维才能完成, 真是让人拍案叫绝.

2. (Block-respecting TMs.)

首先, 按照注释中的方法构造一个 2-tape 图灵机, 则显然可证明 B(n) 与 T(n) 满足 “time-and space-constructibility”.

然后, 确定图灵机 M’ 的纸带数量为 $3*k$. 对于图灵机 M 中的每个纸带, 将对应图灵机 M’ 中的三个纸带. 这三条纸带均是 B(n)-block-respecting 的, 按以分别为如下三个纸带:

1. 第一个块为空, 内容从第二个块开始填写, 其中第 i 个块的内容为 M 中纸带的第 i - 1 个块的逆序.
2. 从最左边的块开始填写内容, 且纸带的内容与 M 中的纸带完全相同.
3. 从最左边的块开始填写内容, 其中第 i 个块的内容为 M 中纸带的第 i + 1 个块的逆序.

最后, 构造图灵机 M’ 的移动方式:

1. 对于图灵机 M 中的每个纸带, 设置一个参数 current, 值域为 $\{1, 2, 3\}$. 表明当前使用这条纸带在 M’ 对应的三条纸带中的哪一条纸带. 即在对于 M 中的纸带 $i$, 将在 M’ 中的 $i_{current}'$ 上以某种方式重现 $i$ 的左右运动, 读取和打孔等操作.
2. 首先令 $current := 2$, 选中第二条纸带进行操作. 如果当前纸带移动到块的最左端后, 仍然需要向左移动, 则不执行此步移动, 转到 3. 如果当前纸带移动到块的最左端后, 仍然需要向右移动, 则不执行此步移动, 转到 4. 此外, 所有的左右移动, 读取, 打孔操作与原纸带完全一致.
3. 令 $current:= 1$.此后的读取, 打孔操作与原纸带一致, 对于纸带的移动, 若原纸带向左移动, 则当前纸带向右移动; 若原纸带向右移动, 则当前纸带向左做移动.
   如果当前纸带移动到块的最右端后, 仍然需要向右移动, 则不执行此步, 而是保持 $current:= 1$, 将所有纸带向左移动到前一个块, 并将 1, 2 纸带的纸带头移动当前块的第一个位置(将第 3 纸带的纸带头移动到块的最后一个位置, 即第 3 纸带不需要额外移动). 当然, 在块间移动需要保证在格之间移动时是合法时刻, 如果不是则需要等待.
   如果当前纸带移动到块的最左端后, 仍然需要向左移动, 则不执行此步, 转到2.
4. 令 $current:= 3$.此后的读取, 打孔操作与原纸带一致, 对于纸带的移动, 若原纸带向左移动, 则当前纸带向右移动; 若原纸带向右移动, 则当前纸带向左移动.
   如果当前纸带移动到块的最左端后, 仍然需要向左移动, 则不执行此步, 而是保持 $current:= 3$, 将纸带 1 向右移动到后一个块, 并逆序写入纸带 2 的当前块中的所有内容; 将纸带 2 向右移动到后一个块, 并逆序写入纸带 3 的当前块中的所有内容; 然后将纸带 3 向右移动到后一个块, 并移动到当前块最后一个位置. 当然, 在块间移动需要保证在格之间移动时是合法时刻, 如果不是则需要等待.
   如果当前纸带移动到块的最右端后, 仍然需要向右移动, 则不执行此步, 转到2.

只有每次移动至少 $B(n)$ 次后, 才会额外移动 $O(B(n))$ 次, 故该方法最后的时间复杂度依然为 $T(n)$.

3. (Improving the Time Hierarchy Theorem via padding.)

a

在长度为 n 的纸带上增加 $f(n) - n$ 个不影响运算的填充字符即可.`

b

设 $TIME(n^3\log^{3/4}n) = TIME(n^3)$, 令 $f(x) = x ^ 4$, 由 a 得到的结论, 可知 $TIME(n^{12}\log^3n) = TIME(n^{12})$.

由于:

$n^{12}\leq 12n^{12}\log n \leq n^{12}\log^3n$

所以:

$TIME(12n^{12}\log n) = TIME(n^{12})$

由 Time Hierarchy Theorem 可知:

$TIME(n^{12}) \neq TIME(n^{12}\times12\log n)$

故矛盾, 所以 $TIME(n^3\log^{3/4}n) \neq TIME(n^3)$,

Homework 2

1. (Almost-Everywhere Time Hierarchy Theorems.)

a