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

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

• 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$. Commented Jan 12, 2022 at 23:27

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.

• There is a simple example that already achieves $2^{\Omega(n)}$: every DNF equivalent to the CNF $\bigwedge_{i<n}(x_i\lor y_i)$ (in $2n$ variables) has at least $2^n$ disjuncts. Commented May 27 at 13:39