布尔函数

对象与记号 ​

一个 $n$ 元布尔函数是函数公理库函数Function · Map · Mapping由定义域、陪域和单值图共同组成，并把每个输入送到唯一输出的映射。

$$f:\{0,1{\}}^n\to \{0,1\}.$$

输入 $x=(x_1,\dots ,x_n)$ 是 $n$ 个 bit 组成的向量，输出是一个 bit。由于定义域是有限集公理库有限集Finite set与某个初始自然数段存在双射的集合。，函数可以由包含 $2^n$ 行的真值表完全指定；公式、程序、多项式和电路则是同一个输入—输出对象的不同表示。

也常把真假编码为 $\{-1,+1\}$，特别是在 Fourier 分析和多项式逼近中。两个编码之间可由 $b\mapsto (-1{)}^b$ 或 $b\mapsto 2b-1$ 转换，但 AND、XOR 与乘法的对应会随约定改变。推导开始前必须声明编码，不能在公式中途把 $0/1$ 与 $\pm 1$ 记法混用。

复杂度通常研究函数族 $\{f_n{\}}_{n\ge 1}$，其中每个 $f_n$ 只处理固定长度输入。单个 $f_n$ 是有限对象；“随 $n$ 增长需要多少资源”属于整个函数族。把一个固定 $n$ 的巨大真值表硬编码为常数，不会推翻关于函数族的渐近下界。

偏函数与关系 ​

偏布尔函数只在 promise 集合 $S\subseteq \{0,1{\}}^n$ 上定义：

$$f:S\to \{0,1\}.$$

算法只需在 $S$ 中的合法输入上满足保证，$x\notin S$ 时可以任意输出或不终止。promise 往往让查询或通信问题显著容易；因此 total function 的定理不能仅凭符号相同就套到 partial function，反方向也不能把 promise 外行为私自补全后仍声称复杂度不变。

关系问题 $R\subseteq S\times Z$ 又是不同对象。它允许同一输入对应多个合法输出，算法只需选择其中一个；这不是“输出不确定的布尔函数”。若输出集合仍是 $\{0,1\}$ 且两个值都可接受，关系在该输入上没有区分要求，而普通函数必须唯一指定一个值。

在两方通信中，还会研究 $f:X\times Y\to \{0,1\}$；那是输入按两位参与者分割的布尔值函数。它与本页的 Boolean cube 函数可以互相编码，却不共享相同的访问模型。通信模型公理库两方通信模型Two-party communication model · Two-party communication complexity model两位参与者各自持有私有输入，只以交换消息协同计算函数或关系，并把通信位数作为核心资源。按交换消息计费，查询模型公理库查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。按读取输入坐标计费，函数本身不替模型决定成本。

支持变量与限制操作 ​

坐标 $i$ 属于 $f$ 的支持，当且仅当存在两个只在第 $i$ 位不同的输入 $x,x^{\oplus i}$，使

$$f(x)\ne f(x^{\oplus i}).$$

对偏函数还要要求 $x,x^{\oplus i}\in S$；promise 外没有可用于证明敏感性的函数值。不在支持中的变量对合法输入的输出从无影响，即使某个表示仍在语法上提到它。函数真正依赖多少坐标是语义性质，不能通过数公式里出现了多少变量名来判断。

把部分坐标固定为常量会得到限制。若 $I\subseteq [n]$，赋值 $\rho \in \{0,1{\}}^I$，则 $f{\upharpoonright }_{\rho }$ 是在其余坐标上代入 $x_i={\rho }_i$ 后得到的函数。限制可逐步暴露局部结构，也是决策树沿一条查询路径后所剩子问题的精确表达。

限制不同于删除一个输入样本。它固定若干坐标并保留与赋值一致的整个子立方体；偏函数的 promise 则可以是任意子集，不必具有子立方体形状。混淆两者会让关于递归和维数的论证失去适用条件。

一个支持可见的例子 ​

定义

$$f(x_1,x_2,x_3)=x_1\oplus x_3.$$

坐标 $1$ 与 $3$ 都在支持中：固定另一个坐标后翻转它们会翻转输出。坐标 $2$ 不在支持中，因为对每个 $(x_1,x_2,x_3)$，只改 $x_2$ 都保持异或结果不变。

取限制 $x_3=0$，得到

$$f{\upharpoonright }_{x_3=0}(x_1,x_2)=x_1.$$

再固定 $x_1=1$ 后，剩余函数恒为 $1$。这条轨迹说明查询已经揭示的 bit 如何把原任务化为更小的剩余函数；若先查询无关的 $x_2$，限制前后函数完全相同，查询没有缩小语义不确定性。

同一 $f$ 可以写成异或门、析取合取式或唯一 multilinear 多项式。某个表示可能重复使用 $x_2$ 后再抵消，也可能把 $x_1\oplus x_3$ 展开成更长公式；这些语法变化不改变支持、真值表或任何只依赖黑盒输入输出的查询复杂度。

失败边界与表示 ​

布尔电路公理库布尔电路Boolean circuit由逻辑门构成的有限无环有向图，计算布尔函数。是计算布尔函数的一种有限有向图表示，不是函数本身。不同电路可计算同一函数，同一电路拓扑换门标签也可计算不同函数。电路大小和深度衡量表示的计算资源；查询复杂度则暂时忽略本地计算，只问需要看多少输入位。

一个固定长度布尔函数也不是形式语言。语言 $L\subseteq \{0,1{\}}^{\ast }$ 同时包含所有长度，可通过特征函数族 $f_n(x)=\mathbf{1}[x\in L\cap \{0,1{\}}^n]$ 与布尔函数联系。漏掉长度索引，会把非一致函数族和由单一算法统一计算的语言混成一件事。

最后，输出只有真假两种并不限制内部结构为两种。一个叶只标 $0$ 或 $1$，算法仍可能需要区分大量会走向同一输出、却在当前访问模型下无法合并的输入。输出集合的基数因此不能单独给出通信或查询上界。

参考资料

• Ryan O'Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014, Chapters 1–2.
• Stasys Jukna, Boolean Function Complexity: Advances and Frontiers, Springer, 2012, Chapters 1–2.
• Ingo Wegener, The Complexity of Boolean Functions, Wiley-Teubner, 1987, Chapters 1–3.