Let $T$ be a truth table of a boolean function $f$ on $n$ input bits. More concretely $T$ could be a list of length $2^n$ such that $T[i] = f(bin(i))$, where $bin(i)$ is the binary representation of the integer $i$.

Now suppose that $T$ is the truth table of a function that has a small $k$-CNF representation, say a $k$-CNF representation with $O(n)$ clauses. Is there an algorithm that computes a $k$-CNF representation of $T$ with $O(n)$ clauses in time $O(2^n)$, i.e. linear in the size of the truth table? The algorithm does not necessarily have to choose the minimum sized representation, but it can't be more than a constant factor larger.

Naively, it is possible to convert $T$ into a CNF by the standard method (negate all zero inputs and and make these clauses) and it is possible to convert a CNF to a $k$-CNF, also by standard methods, but it is not clear that this method gives good guarantees on the size of the resulting $k$-CNF.

I apologize that I have not thought more about the solution before asking. I just want to make sure that the solution is not trivial (or unlikely based on complexity theoretic assumptions).

  • 2
    $\begingroup$ This looks like a relevant paper. [1] Minimizing DNF formulas and AC/sup 0//sub d/circuits given a truth table $\endgroup$ – Mikolas Dec 13 '16 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.