Simplest combination of logic gates to produce a given set of outputs

Question

Given a truth table for a truth function that takes n inputs and produces a single output (true or false), what is the fastest way to find the simplest combination of logic gates that will output the given truth table?

A few rules for specificity:

• Any binary truth function may be used as a logic gate. In other words, AND, OR, XOR, NOR, and NAND are all valid logic gates, but a binary truth function like AND(NOT(A), B) also counts as a single logic gate when determining the simplicity or complexity of a solution.
• The "simplest" solution is the one which uses the fewest logic gates
• The output of a logic gate may either be the output, or it may be an input to exactly one other logic gate.

Primary inputs themselves may go to more than one logic gate; it is only the output of a logic gate that may only be used once. I am most concerned with the minimal circuit necessary for the binary multiplication of two numbers. Do we know of a minimal circuit for multiplication? If so is there an efficient algorithm to construct the minimal circuit?

Answer 1

This problem is discussed in Circuit Minimization Problem, by V. Kabanets and J.-Y. Cai.

Obviously the decision version is in NP (does there exists a circuit of size $\le k$ which agrees with the given truth table), since you could provide the circuit $\mathcal{C}$ and verify that $\forall x\in\left\{0,1\right\}^n : \mathcal{C}(x)=f(x)$. This can be done in polynomial time (relative to the input's size), since the size of the truth table is $2^n$.

It's an open question how hard the problem is. The above paper shows that any proof that this problem is in $P$, or any proof that it is $NP$-complete, would extend our current knowledge and imply a solution to long-standing open problems in complexity theory.

If the Circuit Minimization Problem is in $P$, then it is shown that $BPP=ZPP$ (so for now, showing your problem is in $P$ is open).

Since this is believed to happen anyway (under the assumption that $P=BPP$), they give more consequences which are less likely. For example, it is enough to show $2^n/n$ circuit lower bound for the class $E$ to obtain a $2^{c\cdot n}$ lower bound (If high circuit complexity functions exist in $E$, then very high circuit complexity functions exist too). They also show how to factor Blum integers efficiently on average (Which, they say, is the strongest evidence for the fact that this problem lies outside of $P$).

If the Circuit Minimization Problem is $NP$-hard (under what they call a "natural reduction", where the reduction's output size depends only on the input's size and not structure) then $BPP\subseteq SUBEXP$ and $BPP=P$ unless the exponential time hypothesis fails.

Answer 2

This is the (optimization version of) the problem of circuit minimization for Boolean functions ; it is known to be $\Sigma^p_2$-complete, so it resides at the second level of the polynomial-time hierarchy. In other words, this problem is hard. See http://users.cms.caltech.edu/~umans/papers/BU07.pdf for more details.