A057241 Circuit cost of the hardest Boolean function of n variables; metric: 2-input AND-gates cost 1, NOT is free, fanout is free, inputs are free, no feedback allowed.

0, 0, 3, 6, 10

Offset: 0

Author

Richard C. Schroeppel, Jan 10 2001

Keywords

• nonn
• nice
• hard
• more

Comments

a(5) <= 23. Boole expansion (Knuth page 52).

XOR costs 3.

a(5) <= 20. Modify procedure used to calculate a(5) in A056287 to add XOR.

a(5) <= 18. Let f = g(xi = h), then cost(f) <= cost(h) + cost(g). This is a generalization of minimum memory operations (xi = xj op xk -- Knuth page 101). Add this for min(cost(g),cost(h)) <= 3.

a(5) <= 17. Add cost(f(xi,xj = xi op1 xj, xi op2 xj)) <= cost(f) + 2 (Knuth page 105).

a(5,17) <= 187 where a(5,c) is the number of functions classes that cost c.

a(5,17) <= 1 (David Ian Stevenson).

a(5) >= 13 Stockmeyer limit for symmetric function S124 (Knuth exercise 7.1.2 - 80 and answer to 20 which clarifies Richard C. Schroeppel's hardest functions).

References

• D. E. Knuth, The Art of Computer Programming, Volume 4A, Addison Wesley, 2011.

Links

• Richard C. Schroeppel, Comments and examples
• David Ian Stevenson, Shorter chains for 185 function classes
• David Ian Stevenson, Table of a(5,c)

Crossrefs

Cf. A056287, A058759.