非一致电路类 P/poly

形式陈述 ​

语言 $L\subseteq \{0,1{\}}^{\ast }$ 属于 $\mathbf{P}\mathbf{/}\mathbf{poly}$，若存在布尔电路公理库布尔电路Boolean circuit由逻辑门构成的有限无环有向图，计算布尔函数。族 $\{C_n{\}}_{n\ge 0}$ 和某个多项式 $p$，使每个 $C_n$ 有 $n$ 个输入、大小至多 $p(n)$，并且

$$\mathrm{\forall }n\mathrm{\forall }x\in \{0,1{\}}^n,C_n(x)=1⟺x\in L.$$

定义不要求存在算法由 $1^n$ 生成 $C_n$；这项缺失正是“非一致”的定义性特征，并与一致电路族公理库电路族一致性Circuit family uniformity要求输入长度 n 对应电路可由统一算法有效生成的条件。形成对照。等价地，存在语言 $L^{\prime }\in \mathbf{P}$、多项式 $q$ 与只依赖长度的 advice 串 $a_n\in \{0,1{\}}^{\le q(n)}$，满足

$$x\in L⟺(x,a_{|x|})\in L^{\prime }.$$

从电路到 advice 可把 $C_n$ 的编码交给统一模拟器；从 advice 到电路则把判定 $L^{\prime }$ 的多项式时间计算展开成电路，并把 $a_n$ 硬接为常量。两种刻画中的多项式界都必须对所有 $n$ 由同一个多项式控制。

直觉 ​

P/poly 允许为每一种输入长度制造一块专用芯片，或附上一份该长度共享的建议。电路可以硬编码关于 $n$ 的信息，却不能针对同长度的每个具体输入分别换电路；所有 $2^n$ 个输入仍由同一个 $C_n$ 处理。它衡量的是非一致电路规模，不是某台普通机器的运行时间。

P公理库复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。 中算法可以对每个长度统一展开出多项式大小电路，所以 $\mathbf{P}\subseteq \mathbf{P}\mathbf{/}\mathbf{poly}$。反向包含没有理由自动成立：一族小电路可能存在，却没有任何有效过程告诉我们第 $n$ 张电路是什么。

例子与边界 ​

任何一元语言 $U\subseteq \{1{\}}^{\ast }$ 都有线性大小的非一致电路族。把它视为二进制语言时，对长度 $n$ 令

$$C_n(x)=[1^n\in U]\wedge \underset{i=1}{\overset{n}{\bigwedge }}{x}_i.$$

电路先检查输入确为 $1^n$，再由一个依赖长度的常量位决定是否接受。若 $U$ 选为不可判定集合，所得语言仍属于 P/poly，却不属于 P，甚至不存在判定算法。这不是悖论；无限不可计算信息被分散在电路族的常量选择中。

相反，一份 advice 不能依赖完整输入 $x$。若允许为每个 $x$ 提供位 $[x\in L]$，所有语言都会被一位建议“判定”，模型将失去区分力；P/poly 只允许同长度输入共享 $a_n$。同样，逐个声称“每张电路都有限”也不够，大小上界必须是输入长度的统一多项式。

非一致不等于随机。电路族和 advice 可以任意但固定，定义中没有成功概率；随机电路若要归入 P/poly，需要先固定随机性并证明对同长度的全部输入同时正确，不能只对每个输入分别选一组好随机位。

推论与应用 ​

P/poly 是讨论小电路存在性、advice complexity 与一致性差异的基准。它与 NP公理库复杂度类 NPNP · Nondeterministic polynomial time由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。 的关系进入 Karp–Lipton 型结果：若 NP 拥有多项式规模电路，会导致多项式层级坍塌；这是一条条件结论，而非已知包含关系的改写。

证明某函数族不在 P/poly 意味着排除了所有多项式规模非一致电路，是比排除某个统一算法更强的电路下界。另一方面，给出非一致电路上界并不直接产生可执行程序，还需另证电路族具有合适的一致生成过程。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, Ch. 6, circuits and advice.
• Richard M. Karp and Richard J. Lipton, “Some Connections Between Nonuniform and Uniform Complexity Classes,” STOC 1980, pp. 302–309.