<p>Since you stated your purpose is considering circuit bounds:</p>

<p>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.</p>

<p>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 <em>exponential</em> 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 <em>linear</em> bound.</p>

CC BY-SA 3.0
2015-07-05T14:59:17.017Z
Ok, then if we use a different algorithm, one that solves the minimum circuit size problem, how would you answer my original question?
Tony Johnson
CC BY-SA 3.0
2015-07-05T21:03:37.130Z
@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.
TigerSpots
CC BY-SA 3.0
2015-07-05T21:05:44.190Z
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.
TigerSpots
CC BY-SA 3.0
2015-07-05T05:12:21.170Z
2015-07-05T05:12:21.170Z
TigerSpots
<p>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.</p>

<p><a href="https://en.wikipedia.org/wiki/Symbolic_execution" rel="nofollow">https://en.wikipedia.org/wiki/Symbolic_execution</a></p>

CC BY-SA 3.0
2015-07-05T05:33:08.017Z
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.
vzn
<circuit-complexity><lower-bounds><boolean-functions><boolean-formulas>
Symbolic Execution of the Quine-McCluskey Algorithim
Tony Johnson
# Symbolic Execution of the Quine-McCluskey Algorithim

(Asked by: username_0 on 2015-07-05)

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>

**Tags:** circuit-complexity, lower-bounds, boolean-functions, boolean-formulas
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2015-07-05. Score: 3

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.

> **Comments:**
> **username_0**: Ok, then if we use a different algorithm, one that solves the minimum circuit size problem, how would you answer my original question?  
> **username_2**: @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.  
> **username_2**: 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.  

---

