# Time complexity to convert a truth table to a boolean circuit

The SAT problem is often explained in terms of truth tables. Given some random boolean circuit, calculate its truth table; does there exist an output of $$1$$ in the truth table?

But how about going the other way? A function problem that inputs a truth table, and asks you to construct a boolean circuit that computes that truth table. Is this NP? Is it P?

• It is neither, because it is not a decision problem. Commented Mar 27, 2023 at 4:58
• It seems a rather trivial problem. Commented Mar 27, 2023 at 6:41

A truth table for $$m$$ variables has $$n=2^m$$ entries. A corresponding sum-of-products expression is made of at most $$2^m$$ terms, each of length $$m$$. So the total complexity of outputting them is $$O(m2^m)=O(n\log n)$$, in terms of the input size. This is polynomial.

As regards minimization of the expression, a possible approach is the Quine–McCluskey algorithm. From Wikipedia "For a function of $$m$$ variables the number of prime implicants can be as large as $$\dfrac{3^{m}}{\sqrt {m}}$$", which is $$O(n^{\log3/\log2})$$, still polynomial. Then "Step two of the algorithm amounts to solving the set cover problem, which is NP-hard". But I could not find an explicit expression of the complexity of the latter.

• (in case the algorithm wasn't clear: it outputs one AND gate for each line in the truth table where the output is 1, then ORs them all together) Commented Mar 27, 2023 at 10:21
• @user253751: the cost of "outputting an AND gate" is unclear; it could be considered to be constant. My answer goes in the way of writing down the formula.
– user16034
Commented Mar 27, 2023 at 10:28

It should be polynomial for k-SAT with k not equal to 2. Otherwise it would exist a polynomial reduction from 2-SAT(that is in P) to an np-complete and than P=NP.

New contributor
user3682770 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.