3
$\begingroup$

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.

https://en.wikipedia.org/wiki/Symbolic_execution

$\endgroup$
  • $\begingroup$ a/the main issue or way to visualize this is the algorithm doesnt give you a (nontrivial) DAG, its a tree. most lower bounds are questions about DAGs. $\endgroup$ – vzn Jul 5 '15 at 5:33
3
$\begingroup$

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.

$\endgroup$
  • $\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$ – Tony Johnson Jul 5 '15 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$ – TigerSpots Jul 5 '15 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$ – TigerSpots Jul 5 '15 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.