login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
0, 0, 3, 6, 10 (list; graph; refs; listen; history; text; internal format)
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 generalisation 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

CROSSREFS

Cf. A056287, A058759.

Sequence in context: A289064 A073910 A115251 * A104617 A104618 A104616

Adjacent sequences:  A057238 A057239 A057240 * A057242 A057243 A057244

KEYWORD

nonn,nice,hard,more,changed

AUTHOR

Richard Schroeppel, Jan 10 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 24 21:05 EDT 2017. Contains 292441 sequences.