4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Welcome to the site! The problem is at least decidable, since you have a fixed, finite number of gates any Boolean function on $n$ variables can be represented (in DNF) as a conjuntion of at most $2^n$ $n$-way disjunctions. But, beyond that, I suspect that "what is the least horribly slow way?" would be more accurate than "what is the fastest way?" ;-) $\endgroup$ – David Richerby Oct 4 '16 at 7:45
  • 2
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – adrianN Oct 4 '16 at 7:48
  • 1
    $\begingroup$ When the truth table is part of the input, the decision version (does a circuit of size $\le k$ exists) is in NP. $\endgroup$ – Ariel Oct 4 '16 at 8:42
  • $\begingroup$ I expanded my previous comment to an answer (which, admittedly, only cites hardness results). It seems we cant put this problem anywhere better than NP. Placing it in P or proving NP-completeness will resolve some open questions in complexity/extend some known results. $\endgroup$ – Ariel Oct 5 '16 at 19:03
2
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I don't think this is correct. It looks like what is proven $\Sigma_2^p$-hard is a different problem: given one boolean circuit, find another boolean circuit that computes the same function but is as small as possible. That's not what this question asks about; in this question, the input is the full truth table, not a boolean circuit. The truth table might be exponentially larger, so the question asked about in this question might (potentially) be exponentially easier -- at least, the existing proof of $\Sigma_2^p$-hardness doesn't seem to carry over straightforwardly. $\endgroup$ – D.W. Oct 5 '16 at 16:39

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.