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

Homework 1

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

a

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

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

b

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

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

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

c

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

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

流程如下:

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

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

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

2. (Block-respecting TMs.)

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

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

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

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

a

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

b

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

由于:

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

所以:

TIME(12n12logn)=TIME(n12)TIME(12n^{12}\log n) = TIME(n^{12})

由 Time Hierarchy Theorem 可知:

TIME(n12)TIME(n12×12logn)TIME(n^{12}) \neq TIME(n^{12}\times12\log n)

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

Homework 2

1. (Almost-Everywhere Time Hierarchy Theorems.)

a