O'Reilly logo

Art of Computer Programming, Volume 4A, The: Combinatorial Algorithms, Part 1 by Donald E. Knuth

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Repeating this process six times will produce the BDD for μ6, which has 103,924 nodes. There are exactly 7,828,354 monotone Boolean functions of six variables (see exercise 5.3.4–31); this BDD nicely characterizes them all, and we need only about 4.8 million memory accesses to compute it with Algorithm S. Furthermore, 6.7 billion mems will suffice to compute the BDD for μ7, which has 155,207,320 nodes and characterizes 2,414,682,040,998 monotone functions.

We must stop there, however; the size of the next case, B(μ8), turns out to be a whopping 69,258,301,585,604 (see exercise 77).

Synthesis in a BDD base. Another approach is called for when we’re dealing with many functions at once instead of computing a single BDD on the fly. The functions ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required