Don Knuth has been studying Boolean Synthesis as part of writing Volume 7 of his opus. He would like solutions to the following puzzle. There are about 600K different boolean functions of 5 variables. (The inputs are 5 independent bits, and the output is 1 bit. Inputs may be permuted or negated, and the output negated, are all counted as the same function.) Under Knuth's metric (B2), all but ~100 of these functions can be computed by circuits with <= 10 gates. He's found circuits with 11 gates for most of the remaining functions, but there are 7 holdout functions. He's got 12-gate syntheses for the holdouts, but is hoping that there are 11-gate circuits. We don't know any good methods for proving the impossibility of 11-gate circuits. The best we know how to do is to run a program that generates all 11-gate ciruits, which is too much computing work right now. The allowed gates are two-input And and two-input Xor; also, Nots may be used freely, and don't count against the total. As usual, the circuits must be DAGs (no feedback or loops), and circuit depth doesn't matter. The seven functions are defined by 32-cell truth tables. The hex values are the 32-bit numbers 01bcda86 067ab314 067abc17 06b5d398 166eb583 1698ac5b 169ae443 Example: the truth table for 01bcda86 is -------x x-xxxx-- xx-xx-x- x----xx- This isn't a Karnaugh map with gray-coded coordinates; the coordinates are simply sequential binary numbers. So input variable A is true in the bottom two rows of the table, variable B is true in rows 2 and 4, variable C is true in the right half of the table, D is true in columns 3,4,7,8, and E is true in columns 2,4,6,8. My first cut at synthesizing 1698ac5b by hand has 16 gates; I'm out of practice. There's a December 5 version of Knuth's "Boolean Basics" at http://www-cs-faculty.stanford.edu/~knuth/fasc0b.ps.gz but I wasn't able to view the postscript. He's promised an updated version with the circuit search programs "soon", probably in a few days. Rich