Matpic
mathematics, in pictures
Concept

Circuit complexity

The fewest and, or and not operations needed to compute a truth function, when a result may be used as often as it is needed. Almost every function needs exponentially many, yet no function anyone can name is proved to need more than a few times its number of letters.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Smallest circuits for four functions of three letters. Four small circuit diagrams, each with three inputs feeding a few two-input gates, computing parity, a selector, majority and exactly-one-true with two, three, four and four gates.

How many gates a truth table needs

Every truth function can be built from gates, and the natural measure of a function is the fewest gates that build it. For three letters the whole answer can be computed: no function needs more than four. For n letters, a count shows that almost every function needs about 2ⁿ/n gates, and a construction shows that none needs more. And for any function anyone can actually write down, the best proof in fifty years says it needs 3.1n.

logic · Truth functions Parity and majority on the cube, and the edges between true and false. Two cubes of three-letter assignments, parity with all twelve edges joining a true and a false corner and majority with 6; Khrapchenko's bound at its best 9.00 against an exact size of 10 and 4.00 against an exact size of 5.

The formula that cannot share

A circuit computes the parity of n letters with a chain of n − 1 exclusive-or gates. A formula in and, or and not, which may use each result only once, needs n² letters at least — a bound Khrapchenko proved by counting the cube's edges between true and false — and exhaustive search over every formula of four letters finds parity sitting exactly on it.

logic · Truth functions

Named alongside it

The objects these essays reach for when they reach for this one.

Lower boundParityBoolean circuitBoolean formulaCauchy schwarzCounting argumentExhaustive searchHypercubeMajorityTruth function

All concepts