计算理论（V）[共13页]

1、计算理论(V) 计算机学院 陈翌佳 姚期智Andrew Yao - 2000年图灵奖 In recognition of his fundamental contributions to the theory of computation, including the complexity-based theory of pseudorandom number generation, cryptography, and communication complexity. 通讯复杂性 Communication Complexity y=1101011010 x=1100111010 “x=y？

2、”的通讯复杂性 给定通讯双方各自n位2进制串x和y，他们需要交换多少位的信息才能判断 x是否等于y？ 定理. Yao, 1979 判断“x=y？”通讯双方需要交换n位信息。 通讯协议(protocol)的数学描述 一个n位“x=y?”通讯协议P是一棵二叉树，其中每个内部节点v包含一个函数 w:0,1left, right或者l:0,1left, right；每个叶节点 包含true, false中的一个值。 给定x和y，通讯过程从树的根开始： 1.如果当前节点包含函数w，那么吴奇隆根据w(x)决定走向哪个儿子节点； 2.如果当前节点包含函数l，那么刘诗诗根据l(x)决定走向哪个儿子节点; 2.

3、一旦到达叶节点，它所包含的true, false值就“x=y?”的结果。 通讯协议(protocol)的数学描述 一个n位“x=y?”通讯协议P是一棵二叉树，其中每个内部节点v包含一个函数 w:0,1left,right或者l:0,1left,right；每个叶节点包 含0,1中的一个值。 通讯协议P的深度depth(P)，即最长的由根节点到某个叶节点的路径长度， 就是整个通讯要交换的信息总量。 在所有计算“x=y?”的协议P中，我们想确定最小的depth(P)。 通讯协议的组合特征 对于协议P中的每个节点v，我们令Rv表示所有能够到达v的(x,y)的集合。 引理 1. 所有叶节点的Rv构成了

4、对0,10,1 的一个划分。 引理 2. 每个叶节点的Rv都是0,10,1中的一个单色组合长方形。 组合长方形 R0,10,1是一个组合长方形，当且仅当存在A,B0,1 使得 R=AB。 R0,10,1是单色的，当且仅当x=y对于所有的x,yR都成立， 或者都不成立。 组合长方形的等价刻画 引理. R0,10,1是一个组合长方形，当且仅当对于任意的 (x,y)R和(x,y)R，我们有(x,y)R 。 通讯协议的组合特征 引理 2. 每个叶节点的Rv都是0,10,1中的一个单色组合长方形。 证明. 单色是显然的。我们证明每个节点的Rv都是组合长方形。 假设(x,y)Rv和(x,y)Rv，我们必须验证(x,y)Rv。对v的深度归纳 证明： 从根节点出发到节点v，P的行为在(x,y), (x,y)和(x,y)上完全一致。 “x=y？”的通讯复杂性 定理. Yao, 1979 判断“x=y？”通讯双方需要交换