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,3

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

Table of n, a(n) for n=0..4.

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.

Sequence in context: A293537 A073910 A115251 * A104617 A104618 A104616

Adjacent sequences: A057238 A057239 A057240 * A057242 A057243 A057244

Keyword

nonn,nice,hard,more

Author

Richard C. Schroeppel, Jan 10 2001

Status

approved