有证明的下界
3 位加法的进位最少要 6 层 NAND:5 层做不出,6 层有现成电路。
结论
| 项 | 值 |
|---|---|
| 函数 | A、B 是 3 位无符号数,c 是 1 位进位输入,输出 [A + B + c ≥ 8] |
| 输入 | 7 位,共 128 种 |
| 门 | 两输入 NAND,个数不限,可以共用,可以接常数 0 / 1 |
| 下界 | 深度 5 做不出 |
| 上界 | 有一个深度 6 的电路,22 个门 |
只说这一个进位函数。不说完整加法器或乘法器的最小深度。
为什么 5 层做不出
- 列出深度 ≤ d 能做出的全部函数,记作 F_d。F_0 是 7 个输入;每加一层,把上一层任意两个函数 NAND 一下加进去。这样不漏任何电路,不管门数和共用。
- 实际个数:F_0 = 7,F_1 = 35,F_2 = 540,F_3 = 84,156。
- 深度 5 的输出 = NAND(两个 F_4 函数),每个 F_4 函数要么已在 F_3,要么是两个 F_3 函数的 NAND。
- 输出为 0 的那些输入上,两个操作数都必须是 1。按这个条件筛,合法的 F_3 操作数对有 1,052,195 对,得到 21,787 种不同的乘积,其中 262 种是极大的。
- 没有任何两个极大乘积能凑出目标函数;更浅的深度也做不出。所以深度 5 不可能。
- 常数没用:NAND(0, x) 恒为 1,NAND(1, x) 等于 NAND(x, x),都不会让剩下的电路更浅。
两套独立程序核过
- 一套原生程序直接扫全部 F_3 对,用时 2.014 秒。
- 一套独立 Python 程序换一种算法:对每个输出为 0 的输入建候选位集再求交,用时 5.277 秒。
- 两套重建了全部输入真值表和 F_3,每个计数和最后的结论都一致。
- 另外用 SAT 求解器(CaDiCaL、Kissat)解对应的 31 门槽位问题,都返回 UNSAT。主证据是上面的完整枚举,不靠 SAT。
深度 6 的电路
- 22 个 NAND,深度正好 6。
- 在全部 128 种输入上和
A + B + c ≥ 8逐个比过,全对。