0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ It is neither, because it is not a decision problem. $\endgroup$
    – Nathaniel
    Commented Mar 27, 2023 at 4:58
  • $\begingroup$ It seems a rather trivial problem. $\endgroup$
    – gnasher729
    Commented Mar 27, 2023 at 6:41

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ (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) $\endgroup$ Commented Mar 27, 2023 at 10:21
  • $\begingroup$ @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. $\endgroup$
    – user16034
    Commented Mar 27, 2023 at 10:28
-1
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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