Karchmer–Wigderson 博弈

形式陈述

令 $f:\{0,1\}^n\to\{0,1\}$ 为非常值函数。Alice 得到 $x\in f^{-1}(1)$ ，Bob 得到 $y\in f^{-1}(0)$ ，双方必须输出某个坐标 $i$ ，使 $x_i\ne y_i$ 。这样的坐标必然存在，否则 $x=y$ 却有不同函数值。搜索关系写作

KW_f=\{(x,y,i):f(x)=1,\ f(y)=0,\ x_i\ne y_i\}.

采用确定性通信复杂度的关系版本：协议树的每个叶公开标记一个坐标，且到达该叶的所有输入对都必须使它成为合法答案。双方只看见自己的输入和已有 transcript； $D^{cc}(KW_f)$ 是在所有这样的正确协议中，最小的最坏通信 bit 数。

Karchmer–Wigderson 定理断言，在二元De Morgan 公式约定下，

D_{\mathrm{form}}(f)=D^{cc}(KW_f).

由公式到协议时保持不变量 $F(x)=1,F(y)=0$ ：根为 OR，Alice 发送一个在 $x$ 上为真的子式编号，而该子式在 $y$ 上也必为假；根为 AND，Bob 发送一个在 $y$ 上为假的子式编号，而它在 $x$ 上必为真。到达叶 $x_i$ 时必有 $x_i=1,y_i=0$ ；到达叶 $\neg x_i$ 时方向相反，但坐标 $i$ 仍是合法答案。反向先删去不可达分支。每个可达结点对应一个非空矩形 $A\times B$ ：Alice 发言只划分 $A$ ，Bob 发言只划分 $B$ 。若一个叶公开输出 $i$ ，则所有 $x\in A,y\in B$ 都满足 $x_i\ne y_i$ ；固定任一 $y$ 可知全部 $x_i$ 相同，全部 $y_i$ 取相反值。因此这一叶能统一选定文字 $x_i$ 或 $\neg x_i$ ，在 $A$ 上为真而在 $B$ 上为假。将 Alice 结点变成 OR、Bob 结点变成 AND，逐层保持这个分离不变量，得到深度不超过协议成本的公式。两个方向的最优值便相等。

直觉

一个真输入和一个假输入不可能在每一位都相同；困难不在分歧是否存在，而在双方各自只看见一半信息时怎样定位它。公式的每一层恰好替一方提供一次局部选择：OR 为真时，真输入持有者知道至少一个真孩子；AND 为假时，假输入持有者知道至少一个假孩子。通信路径因而逐层缩小到一个文字，最长 transcript 就是根到叶最长路径。

这个翻译把语法深度变成一个语义搜索问题。证明公式深度下界时，不必枚举所有树形表达式；只要证明任何协议都必须交换很多 bit。反过来，一个巧妙协议会机械地给出浅公式。

逐结点翻译直接给出公式树；但在相同二元门基和深度计数下，若不限制规模，把单输出 DAG 从输出向输入展开为树不会增加深度，只可能复制大量共享子计算。反过来公式本就是电路，因此最小公式深度等于最小电路深度，KW 也刻画这个共同的深度最优值。

Karchmer–Wigderson 博弈：公式求值—通信协议逐层对应图 — Karchmer–Wigderson 博弈示意图

例子与边界

取 $f(x)=x_1\lor x_2\lor x_3\lor x_4$ 。Bob 的假输入只能是 $0000$ ；Alice 收到例如 $x=0101$ 。按平衡 OR 公式，Alice 先发送一 bit 表示选择前半 $(x_1,x_2)$ ，再发送一 bit 选择其中的 $x_2$ ，输出坐标 $2$ 。若约定总挑最小的为真坐标，这对所有真输入形成深度 $2$ 的确定协议；其四个可能输出叶对应平衡四叶 OR 公式。公开叶输出的要求在这里不可省略：若只让 Alice 本地输出，她已能自行找出一个 $1$ 坐标，通信可以为零。按本页约定，一般 $OR_n$ 的成本为 $\lceil\log_2 n\rceil$ ，与最小二元 OR 树深度一致。

对单调 $f$ ，单调 KW 关系要求输出 $x_i=1,y_i=0$ 的坐标。若不存在，则逐坐标有 $x\le y$ ，单调性会推出 $f(x)\le f(y)$ ，与 $1>0$ 矛盾。这个版本刻画单调公式深度；单调公式是单调电路中 fan-out 为 $1$ 的特例。对非单调函数不能要求固定方向的 $1\to0$ 分歧，例如 parity 的真、假输入可能只在 $0\to1$ 方向不同。

KW 是关系问题而非双方共同计算一个单值函数；输出任一合法坐标即可。二元公式中选择孩子只需发送一 bit，因此通信位数与门深度逐层一致；若直接允许 $r$ 扇入门，一次选择可能需要 $\lceil\log_2r\rceil$ bit，精确等式必须随深度 convention 调整。随机协议、量子协议、允许错误的协议各对应不同资源，不能无条件替代上面的确定性精确等式。协议树的叶数也能联系公式规模，但本页的资源是通信深度；以正反例集合和显式叶预算为状态的公式规模博弈是另一套刻画，不能把两页合并成同义定义。

推论与应用

单调 KW 博弈最初用于证明 $s$ - $t$ 连通性的单调二元电路及公式需要超对数深度：通信者必须从一张连通图和一张不连通图中找出方向正确的分歧边，图的割结构使搜索无法用太少通信位完成。该结论允许 DAG 共享，但不覆盖允许否定的一般连通性电路；共享不会避开这个深度下界，也不能由此直接宣称单调 DAG 需要超多项式规模。

在 NC¹ 研究中，KW 视角把公式深度下界、协议组合与函数复合放到同一语言。若能证明复合函数的 KW 通信复杂度近似相加，就会得到更强公式下界，这也是 Karchmer–Raz–Wigderson 复合猜想一类问题的动机。它们仍是开放研究路线，不能写成已经给出超多项式一般电路下界的定理。

参考资料

Mauricio Karchmer and Avi Wigderson, “Monotone Circuits for Connectivity Require Super-Logarithmic Depth,” SIAM Journal on Discrete Mathematics 3(2), 1990, pp. 255–265.
Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, §1.5.
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, §13.5.4.

形式陈述 ​

反向链接

形式陈述