21 NAND Docs 中文

Proven lower bounds

The carry of a 3-bit addition needs at least 6 levels of NAND: 5 levels cannot do it, and a 6-level circuit exists.

Result

ItemValue
FunctionA and B are 3-bit unsigned numbers, c is a 1-bit carry input, output [A + B + c ≥ 8]
Inputs7 bits, 128 combinations in total
GatesTwo-input NAND, any number, can be shared, can connect to constant 0 / 1
Lower boundDepth 5 cannot do it
Upper boundThere is a depth-6 circuit with 22 gates

This covers only this one carry function. It says nothing about the minimum depth of a full adder or multiplier.

Why 5 levels cannot do it

  1. List every function that can be built with depth ≤ d, and call the set F_d. F_0 is the 7 inputs. For each new level, NAND any two functions from the level before and add the result. This misses no circuit, whatever the gate count or sharing.
  2. Actual counts: F_0 = 7, F_1 = 35, F_2 = 540, F_3 = 84,156.
  3. A depth-5 output = NAND(two F_4 functions). Each F_4 function is either already in F_3, or the NAND of two F_3 functions.
  4. On the inputs where the output is 0, both operands must be 1. Filtering by this condition leaves 1,052,195 valid pairs of F_3 operands, giving 21,787 distinct products, of which 262 are maximal.
  5. No two maximal products can make the target function, and shallower depths cannot either. So depth 5 is impossible.
  6. Constants do not help: NAND(0, x) is always 1, and NAND(1, x) equals NAND(x, x). Neither makes the rest of the circuit shallower.

Checked by two independent programs

The depth-6 circuit