5.1 电路复杂性与下界

5.1 电路复杂性与下界

本节摘要：图灵机难证下界，电路模型更具体。本节讲清楚电路复杂性、P/poly 类、AC0/Razborov 下界、自然证明障碍、以及为什么电路下界是分离类的关键。读完你能理解为什么"证明电路下界难"本身是个深刻问题。

一、电路模型（下）

布尔电路是计算的具体模型——由与/或/非门组成的无环网络，输入位进，输出位出。

电路 vs 图灵机：

• 电路是"硬件"——固定计算某长度输入，不同输入长度要不同电路。
• 图灵机是"软件"——一个机器处理所有长度输入。

电路族 {Cₙ} 处理所有长度——Cₙ 处理 n 位输入。电路大小（门数）和深度（最长路径）是复杂性度量。

二、电路复杂性的类

P/poly：多项式大小电路族可解的类。等价于多项式大小建议（advice）的多项式时间图灵机——建议是只依赖输入长度的辅助信息。

P ⊆ P/poly——确定性多项式算法能转电路（用电路模拟算法的每步）。但 P/poly 可能更大——电路能用非构造性建议。

P/poly 包含一些不可计算问题（如任何长度特定的建议），所以 P/poly 不全是"可解"。

NC（Nick's Class）：多项式大小、对数深度电路。NC 是"高效并行"的类——能并行多项式多处理器多项式时间（对数深度）解。NC ⊆ P（对数深度电路转多项式时间算法）。

AC⁰：常数深度、多项式大小、与/或/非门电路。最弱的电路类——不能计算奇偶性（XOR）。

三、电路下界

证明 P ≠ NP 的一种思路：证明 NP 问题（如 SAT）没有多项式大小电路——即 SAT 电路大小超多项式。

但电路下界极难证。已知结果：

AC⁰ 下界：Furst-Saxe-Sipser 和 Ajtai 独立证明 AC⁰ 不能计算奇偶性（XOR）——任何 AC⁰ 电路算 XOR 要超多项式大小。这是第一个非平凡下界。

Razborov 下界：Razborov 1985 证明 AC⁰[p]（AC⁰ 加 mod p 门）不能计算 mod q（p≠q 素数）——单调电路下界。

单调电路下界：Razborov 证明团问题（判断图是否有 k 团）需要指数大小单调电路。但非单调电路下界未知。

自然证明障碍：Razborov-Rudich 1994 证明：任何"自然"的电路下界证明方法不能分离 P/poly 和 NP——因为自然方法会破坏伪随机函数的存在（假设存在）。这解释了为什么电路下界进展停滞——现有方法都是"自然"的，被障碍挡住。

四、为什么电路下界难

电路下界难证的原因：

1. 电路灵活：电路可任意重组，不像图灵机有固定结构，下界要考虑所有可能电路。

2. 计数论证弱：计数电路数量给下界（多数函数要大电路），但具体函数（如 SAT）不能直接用计数。

3. 自然证明障碍：现有"自然"方法被障碍挡，需要"非自然"方法，但难找。

4. 对角化局限：对角化（用于 P≠EXPTIME）对电路类不直接适用，因为电路类不闭合于对角化。

5. 已知下界弱：最强下界是 AC⁰[p] 的 mod q 下界，对一般电路（NC¹ 以上）几乎没有下界。

五、电路下界的意义

电路下界是分离类的关键：

1. 分离 P 和 NP：证明 SAT 无多项式电路即 P ≠ NP（电路版）。
2. 分离 NC 和 P：证明某 P 问题无对数深度电路，分离并行和串行。
3. 去随机化：电路下界（如 SAT 指数下界）能去随机化 BPP（Impagliazzo-Wigderson）。
4. 密码学：电路下界是单向函数存在的必要条件，密码学基础。

所以电路下界不仅是技术问题，是分离类、去随机化、密码学的基础。但自然证明障碍让进展停滞，需要新方法。

六、当前进展和方向

AC⁰ 下界：成熟，对低深度电路有完整理论。

AC⁰[p] 下界：Razborov-Smolensky，对带 mod p 门的常数深度电路有下界。

TC⁰ 下界：阈值电路（带 majority 门），多数下界未知，是当前焦点。

自然证明障碍：解释停滞，引导寻找非自然方法（如代数复杂性、几何复杂性）。

代数复杂性：用代数电路（多项式计算）证明下界，如永久式 vs 行列式（Valiant 猜想），是另一条路。

七、一个电路例子：奇偶函数

用电路实现奇偶函数最能说明 AC⁰ 的局限。n 位奇偶函数是把所有输入位异或起来，直觉上用树状异或门，深度为对数 n。但异或门不是"与或非"基本门——把它展开成与或非要付出代价。Furst-Saxe-Sipser 与 Ajtai 的经典结论是：任何常数深度、多项式大小的与或非电路都无法计算奇偶函数；事实上，深度为 d 的电路要计算奇偶，大小至少是 2 的 n 的 d-1 分之一次方的指数量级。这就是"AC⁰ 不能算异或"的具体含义。

# 奇偶函数的最优电路结构（示意）
层1: 相邻位两两异或（用与/或/非展开）
层2: 结果继续两两异或
...
深度为 log n 的树，总门数 O(n)
# 但对常数深度电路，同样任务需要超多项式门数——这正是下界定理的内容
​

这个例子的意义在于：它给出了一个"具体函数加具体电路族"的确定性下界，是电路复杂性少有的完整成功案例，也是通往更一般下界的模板。

八、为什么 P/poly 能包含不可计算问题

P/poly 允许"建议串"随输入长度变化，这让它能包含某些不可计算的问题。例如，定义一个语言：长度为 n 的建议串直接编码"第 n 个图灵机是否停机"的答案。图灵机没法算出这个建议串，但电路族可以"免费"接收它——于是这个不可计算语言也落在 P/poly 里。这个反直觉的事实说明：P/poly 不是"可计算"的代名词，而是"存在多项式大小电路"的宽松类。也正因如此，证明"NP 不包含于 P/poly"才是真正有意义的强下界——它比 P 不等于 NP 更强。

⚠️ 常见误读：以为"电路下界就是图灵机下界"。电路模型更具体但也更灵活，下界证明方法和图灵机不同，且自然证明障碍让电路下界特别难。

💡 关键直觉：电路是计算的具体模型，P/poly 是多项式电路类（含 P，可能更大）。电路下界是分离类的关键（SAT 无多项式电路即 P≠NP 电路版），但自然证明障碍（Razborov-Rudich）挡住现有方法。已知下界弱（AC⁰ 不能算 XOR，AC⁰[p] 不能算 mod q），对一般电路几乎无下界。需要非自然方法（代数复杂性等），是去随机化和密码学的基础。

核心回顾

• 电路模型：与/或/非门无环网络，电路族处理所有长度，大小/深度为度量。
• P/poly：多项式大小电路，含 P，可能更大，含非构造性建议。
• NC：多项式大小对数深度，高效并行，NC⊆P。
• AC⁰：常数深度多项式大小，不能算 XOR（Furst-Saxe-Sipser/Ajtai）。
• 电路下界：分离 P/NP 的电路版，去随机化基础，密码学基础。
• 自然证明障碍：Razborov-Rudich，现有自然方法不能分离 P/poly 和 NP，解释停滞。
• 难证原因：电路灵活、计数弱、自然障碍、对角化局限、已知下界弱。
• 方向：AC⁰ 成熟、AC⁰[p] 有下界、TC⁰ 焦点、代数复杂性（永久式 vs 行列式）另一条路。