Reducing a CNF formula to a DNF formula in less than exponential time

Question

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}$.

Answer 1

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.