1
$\begingroup$

The easy way is by looking at the $\{0,1\}$-table and construct the corresponding DNF formula from that, but this will take $2^n$ time. I want to do it much more efficiently.

My idea is based upon the following idea: lets take $2$ clausers $C_1 = ( l_{1,1} \vee l_{1,2} \vee ... \vee l_{1,k})$ and $C_2 = ( l_{2,1} \vee l_{2,2} \vee ... \vee l_{2,k})$. I construct a DNF version in the following way:

First we write this as $$ \left(( l_{1,1} \vee l_{1,2} \vee ... \vee l_{1,k})\wedge l_{2,1}\right) \vee ... \vee \left(( l_{1,1} \vee l_{1,2} \vee ... \vee l_{1,k})\wedge l_{2,k}\right)$$

Then I write this as: $$ \left( l_{1,1} \wedge l_{2,1}\right)\vee ... \vee \left( l_{1,n} \wedge l_{2,1}\right) \vee ... \vee \left( l_{1,1} \wedge l_{2,k}\right)\vee ... \vee \left( l_{1,n} \wedge l_{2,k}\right)$$

So far the amount of clauses I have is $k^2$.

If we continue the same process to the next clause, we will have $k^3$ clauses of size $3$ each.

Eventually, if we had $m$ clauses to begin with, we will construct $k^m$ clauses of size $m$ each.

This is a major blow of the size of the formula, might be even worse than simply looking at the $\{0,1\}$-table.

Any better attempts? Preferably something that will take less than $2^n$, even less than $2^\frac{3n}{4}$.

$\endgroup$
1
  • $\begingroup$ Since deciding the satisfiability of a DNF formula can be done in polynomial time in the size of the formula and since SAT is $\mathsf{NP}$-complete, I doubt you could find a less than exponential time algorithm. However, there may be some $\mathcal{O}(\alpha^n)$ algorithm for $\alpha < 2$. $\endgroup$
    – Nathaniel
    Jan 12 at 23:27
2
$\begingroup$

Miltersen, Radhakrishnan and Wegener construct, in their paper On converting CNF to DNF, a function which has a polynomial size CNF, but whose smallest DNF has size $2^{n-\Theta(n/\log n)}$.

In particular, even if the input CNF has polynomial size, you cannot expect to do better than exponential time, since the output might be that long.

$\endgroup$

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.