If I understand correctly, the Quine–McCluskey algorithm will find the minimum boolean formula size for given boolean function. Has there been any attempts to (for lack of a better term) symbolically execute the algorithm with a class of boolean functions rather than a single one to find a circuit unconditional lower bound? Just curious to see if anybody has tried this before, and if so,(presumably) why it wouldn't work.
1 Answer
Since you stated your purpose is considering circuit bounds:
Taking a boolean function and "minimizing" using Karnaugh maps or the Quine–McCluskey algorithm, then converting the formula to AND and OR gates will give you a circuit calculating that function. This however does not actually give you a minimum sized circuit. Karnaugh maps minimize the number of product terms in the sum of products form of specifying a function, this is NOT the same as minimizing the number of gates in a circuit.
Consider for instance the $N$ input parity function. The sum of products form will have $2^{N-1}$ minterms, which means you'd need an exponential number of gates using this method. However if it takes us $M$ of whatever gates are your basis to make a 2-input XOR gate, we can make the $N$ input parity function with only $M(N-1)$ gates: a linear bound.
-
$\begingroup$ Ok, then if we use a different algorithm, one that solves the minimum circuit size problem, how would you answer my original question? $\endgroup$ Jul 5, 2015 at 14:59
-
1$\begingroup$ @TonyJohnson I personally don't know of a way of solving the minimum circuit size problem short of naive searching the entire space adding more and more gates. Even not asking for an actual solution, but just a non-trivial lower bound, is very difficult. Without specifying what this "different algorithm" may be, its not really possible to discuss if it could help come up with better bounds. $\endgroup$ Jul 5, 2015 at 21:03
-
1$\begingroup$ Maybe you could ask a separate question about algorithms which solve the minimum circuit size problem. I'd be curious to learn more about the current state-of-the-art myself. $\endgroup$ Jul 5, 2015 at 21:05