信息论 | 5 复杂度理论

Concept	Object	Consideration
entropy	random object	minimun description length (bits)
Kolmogorov complexity	deterministic object	minimun description length (bits)
Communication complexity	boolean functions	minimum communication length (bits)

8 Kolmogorov Complexity

Entropy 将研究限制在 (离散) 随机变量上, Kolmogorov 复杂度将研究限制在字符串空间 (string space) 上: \[ \{0,1\}^* := \bigcup_{n=0}^\infty \qty{0,1}^n. \] 想法是用一个算法生成该字符串, 然后去分析该算法.

8.1 Decision problems

考虑一个问题: 给定一个子集 \(L\in2^{\{0,1\}^*}\) 和任意字符串 \(x\in\{0,1\}^*\), 问: 是否有 \(x\in L\)? 这称为判定问题 (decision problem). 假设我们有一个算法来解决该问题, 则算法 \(a\) 也是一个字符串, \(a\in\{0,1\}^*\).

然而, 算法的数量要比问题的数量少得多. 注意到: \[ \operatorname{\rm card}(2^{\{0,1\}^*}) > \operatorname{\rm card}(\{0,1\}^*), \] 换言之, 几乎所有问题都是不可计算的. (实际上, \(\operatorname{\rm card}(\{0,1\}^*)=\aleph_0\), 而 \(\operatorname{\rm card}(2^{\{0,1\}^*})=2^{\aleph_0}\).)

8.2 Kolmogorov complexity

字符串 \(x\in\{0,1\}^*\) 的 (关于通用图灵机 \({\cal U}\) 的) Kolmogorov 复杂度 (K-复杂度) 定义为输出 \(x\) 的最短代码 (算法) 长度: \[ K_{\cal U}(x) := \min_{\substack{p\in\{0,1\}^*\\{\cal U}(p)=x}} \abs{p}. \] 该 universal Turing maching \({\cal U}\) 可以理解为一种程序设计语言. 实际上, 我们有如下结论:

• 对任意 UTM \({\cal U},{\cal U}'\), 存在常数 \(C\), 使得对任意字符串 \(x\in\{0,1\}^*\), 成立 \[ K_{\cal U}(x) \leq K_{\cal U'}(x) + C. \] 常数 \(C\) 就是用 \({\cal U}\) 实现 \({\cal U}'\) 的代码长度.

Theorem Kolmogorov 复杂度 \(K_{\cal U}(x)\) 不可计算.

Pf 假设存在一个算法 \(p_0\) 可以计算 \(K_{\cal U}(x)\), 不妨设 \(|p_0|=1000\). 我们构造一个这样的程序 \(p_0'\), 使得它的长度和 \(p_0\) 相似, 比如 \(|p_0'|\approx1050\), 但是却可以输出一个 K-复杂度很大, 比如 \(\geq10^{10}\) 的字符串 \(x\), 这样就得到了矛盾: \(1050\approx|p_0'|\geq K(x)\geq 10^{10}\).

程序 \(p_0'\) 可以构造如下:

• 从长度为零开始, 枚举所有字符串 \(x\in\{0,1\}^*\):
  • 利用 \(p_0\) 判断, 如果 \(K(x)\geq10^{10}\), 则输出 \(x\).

该程序比 \(p_0\) 长不了多少.

9 Communication Complexity

考虑布尔函数 \(f:\{0,1\}^{2n}\to\{0,1\}\), Alice 和 Bob 分别拥有 \(x\in\{0,1\}^n\) 和 \(y\in\{0,1\}^n\) (\(n\) bit 字符串), 他们想要计算 \(f(x,y)\). 在最糟糕的情况下, 两人至少需要通信的 bit 数称为 \(f\) 通信复杂度 (communication complexity).

9.1 Partition

例如 \(f_{\textsf{eq}}(x,y):=\Cases{1,&x=y,\\0,&x\neq y.}\) 将 \(f\) 的所有取值排成一张 \(2^n\times2^n\) 的表 (这里以 \(n=2\) 为例): \[ \begin{array}{c|cccc} & 00 & 01 & 10 & 11 \\ \hline 00 & \orange{1} & 0 & 0 & 0 \\ 01 & 0 & \orange{1} & 0 & 0 \\ 10 & 0 & 0 & \orange{1} & 0 \\ 11 & 0 & 0 & 0 & \orange{1} \\ \end{array} \] 每次通信传递 1 bit 信息, 者相当于将矩阵 (沿若干横线 / 若干竖线) 分成两部分 (分别对应该 bit 为 \(0\) 和 \(1\) 的情形, 两部分不一定一样大, 也不一定连续, 但须由矩形组成. 划分方式是事先约定好的 protocol), 只保留其中一个部分. 经过若干次划分后, 若剩下的矩形中全为 \(0\) 或全为 \(1\) (等值矩形), 便计算好了 \(f(x,y)\).

设某个通信协议的等值矩形数量为 \(R\), 则该协议在最差情况下所需的通信 bit 数至少为 \(\log{R}\). 最优的通信协议应当是等值矩形数量最少的: \[ \chi(f) := \min_{\textsf{all protocols}} R. \] 因此, 通信复杂度 (最优协议下的最差情况) 的下界为:

Theorem (通信复杂度下界) \(\operatorname{CC}(f) \geq \log\chi(f)\).

观察上面的矩阵, 可以发现对角线的元素 (一共 \(2^n\) 个), 任意两者都不能属于同一个等值矩形, 因此 \(R\geq2^n\), 通信复杂度 \[ \operatorname{CC}(f_{\textsf{eq}}) \geq \log\chi(f) \geq \log(2^n) = n. \] 很容易构造出传输 \(n\) bit 的通信协议 (传输 \(x\) 的每个 bit 即可), 因此 \(\operatorname{CC}(f_{\textsf{eq}})=n\).

看另外一个例子, \(f_{\textsf{disjoint}}:=\Cases{1,&x\wedge y=0,\\0,&\textsf{otherwise}.}\) (判断 \(1\) 的位置是否不交.) 将矩阵画出来 (以 \(n=2\) 为例), \[ \begin{array}{c|cccc} & 00 & 01 & 10 & 11 \\ \hline 00 & 1 & 1 & 1 & \orange{1} \\ 01 & 1 & 0 & \orange{1} & 0 \\ 10 & 1 & \orange{1} & 0 & 0 \\ 11 & \orange{1} & 0 & 0 & 0 \\ \end{array} \] 副对角线的元素 (共 \(2^n\) 个), 任意两者不能处于同一个等值矩形中, 同上有 \(\operatorname{CC}(f_{\textsf{disjoint}})=n\).

9.2 Rank

下面我们来计算一般的 \(f\) 的等值矩形的数量. 记 \(f\) 对应的矩阵为 \(M(f)\in M_{2^n}(\Bbb{F}_2)\).

Theorem 最小等值矩形数量 \(\chi(f) \geq \rank M(f)\).

Pf 将 \(M(f)\) 分成若干矩阵 \(M_i\) 的和, 其中 \(M_i\) 只包含一个 \(1\)-等值矩阵 (\(i=1,2,\dots,\chi(f)\)). 则 \[ \rank M(f) = \rank\!\pqty{\sum M_i} \leq \sum\rank{M_i} = \chi(f). \]

9.3 Randomized algorithms

承接上面的 \(f_{\textsf{eq}}\) 的计算问题.

Alice 和 Bob 分别有二进制序列 \(x=(x_0,\dots,x_{n-1})\) 和 \(y=(y_0,\dots,y_{n-1})\), 它们想要知道 \(x,y\) 是否相等. 我们已经证明, 在最糟糕的情况下, 两人至少需要通信 \(n\) bit. 下面我们介绍一种随机算法 (randomized algorithm), 它有一定 (很小) 的概率发生错误, 但可以达到比理论值好得多的传输效率.

随机算法:

• 取素数 \(p\in[n^{100},n^{101}]\).

• 随机 (uniform) 挑选 \(t\in\Bbb{F}_q\equiv\{0,1,\dots,p-1\}\).

• 通信过程:

  1. Alice 构造多项式 \(f(T):=x_0+x_1T+\cdots+x_{n-1}T^{n-1}\in\Bbb{F}_p[T]\).

  2. Alice 计算 \(f(t)\).

  3. Alice 将 \(t\) 和 \(f(t)\) 传输给 Bob.

     • 只需要传输 \[ 2\times\log(n^{101}) = \mathcal{O}(\log{n})\;\textsf{bit}, \] 远远小于 \(n\) bit.

  4. Bob 构造多项式 \(g(T):=y_0+y_1T+\cdots+y_{n-1}T^{n-1}\in\Bbb{F}_p[T]\).

  5. Bob 计算 \(g(t)\).

  6. Bob 比较 \(f(t)\) 和 \(g(t)\).

     • 若 \(f(t)\neq g(t)\), 则当然有 \(x\neq y\).
     • 若 \(f(t)=g(t)\), 我们认为有 \(x=y\). (有一定的概率发生错误.)

下面分析错误的概率. 发生错误当且仅当 \(x\neq y\) 且 \(f(t)=g(t)\), 也就是我们挑选的 \(t\) 刚好是多项式 \[ h(T) := f(T) - g(T) \] 的根. 因为 \(h(T)\) 至多有 \(n-1\) 个根 (可能有重根), 所以恰好选中 \(h(T)\) 的根的概率不超过 \[ \frac{n-1}{p} \leq \frac{n-1}{n^{100}} \approx n^{-99}. \]