Notes from Richard Schroeppel (rcs(AT)CS.Arizona.EDU) concerning A057241
Tue, 9 Jan 2001

I'll offer the sequence 0,0,3,6,10, <=23.
"Circuit cost of hardest boolean functions of N inputs.
Metric: 2-input And-gates cost 1, Not is free,
Fanout is free, Inputs are free, no feedback allowed."

The next term may be pretty hard to compute.
The 10 took several weeks of Alpha time, and the following term
is thousands (millions?) of times harder.  (There are more than half a
million functions of five variables; you have to locate a function
that requires an alleged maximum gate count, do the search to
show it can't be done in fewer gates, and supply no-worse circuits
for all the other functions.)

Examples:

f(0) = 0.  Example F() = 0 (or 1).  The null circuit suffices for
computing constants.

f(1) = 0.  Example F(A) = A.  Again, the null circuit suffices for
copying an input.

f(2) = 3.  Example F(A,B) = A xor B.
Circuit:  (A and (not B)) or ((not A) and B).
Cost = 3, for two Ands plus one Or; the Nots are free.

f(3) = 6.  Two examples F(A,B,C) = A xor B xor C;
G(A,B,C) = "true (1) when A+B+C=2".
Circuit for F is built from C xor (A xor B).
Circuit for G computes (A and B),(~A and ~B),((A and B) or (~A and ~B)),
(~C and (A and B)), (C and ~((A and B) or (~A and ~B))), followed
by the Or of the last two expressions.

F(4) = 10.  There are only four functions that require the maximum ten gates:

  - - - X    - - - X    - - - X    - - - X
  - X X -    - X X -    - X X -    - X X -  
  - X X -    - X X -    X - - -    X - - -
  X - - X    X - X X    - - - X    - - X X

Finding reasonable descriptions is a stretch; I've settled on
F(A,B,C,D) = "A+B+C+D=2 or 4"
G(A,B,C,D) = "A selects carry or low bit of B+C+D"
H(A,B,C,D) = "the binary number ABCD is 1 mod 3"
I(A,B,C,D) = "the binary number ABCD is 1 mod 3 or else 0"
These requires some morphing to get the truth tables shown.
My Alpha search program ran through all the 9-gate circuits.
These four functions were left, and I found 10-gate circuits by hand.

    is any circuit allowed?  what components are allowed?
    ("or"s ?, etc)

Circuits are built from two-input And and one-input Not.
Of course any boolean function can be built from these.
Not is free, so you can assume Or is available for the same cost
as And.  The circuit must be a rooted DAG, with the input
variables as leaves.  The no-feedback restriction is probably
important for larger circuits, but I didn't want to choose a
definition for how feedback behaves.  I know that in the multiple-
output case, there's an example where feedback gives a smaller
circuit, so I'm guessing it also happens in the single-output case.


There's a nice book from the mid-80's called "Complexity of
Boolean Circuits" with a wonderful bibliography, but the
author concentrates on asymptotic issues, and doesn't
say much about small cases.

[I. Wgener, Complexity of Boolean Circuits, Wiley, 1987;
P. E. Dunne, Complexity of Boolean Networks, Acadeic Press, 1988.]

My main interest in the problem is a belief that the hardest
functions might be interesting, although the evidence from the
4-variable case is dubious support.  Otoh, the search for
Busy-Beaver(5) turned up some interesting unexpected long-running
Turing Machines.

Rich   rcs(AT)cs.arizona.edu