%I #41 May 12 2024 11:42:21
%S 0,0,3,6,10
%N 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.
%C a(5) <= 23. Boole expansion (Knuth page 52).
%C XOR costs 3.
%C a(5) <= 20. Modify procedure used to calculate a(5) in A056287 to add XOR.
%C 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.
%C a(5) <= 17. Add cost(f(xi,xj = xi op1 xj, xi op2 xj)) <= cost(f) + 2 (Knuth page 105).
%C a(5,17) <= 187 where a(5,c) is the number of functions classes that cost c.
%C a(5,17) <= 1 (David Ian Stevenson).
%C 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).
%D D. E. Knuth, The Art of Computer Programming, Volume 4A, Addison Wesley, 2011.
%H Richard C. Schroeppel, <a href="/A057241/a057241.txt">Comments and examples</a>
%H David Ian Stevenson, <a href="/A057241/a057241_1.txt">Shorter chains for 185 function classes</a>
%H David Ian Stevenson, <a href="/A057241/a057241_2.txt">Table of a(5,c)</a>
%Y Cf. A056287, A058759.
%K nonn,nice,hard,more
%O 0,3
%A Richard C. Schroeppel, Jan 10 2001