[Solved]: Which CNF boolean formulas blow up exponentially at conversion to DNF?

Problem Detail: 

If I'm correct, some boolean formulas in CNF require exponential size when being converted to an equivalent DNF version (and vice versa).

But what is an example of such a formula (and is there a general way to capture their structure - if the first question is too easy, and I'm just too stupid to see it)?

In this post, the parity function is discussed as an example of a function which blows up exponentially when converted to both CNF and DNF from a non-NF version: Formulas for which any equivalent CNF formula has exponential length

But what about just CNF <=> DNF? And how frequent are these "bad" formulas? (Very rare, I'd suspect, but can it be proved?)

Asked By : lukas.coenig

Answered By : Yuval Filmus

The classical example is $$(x_1 \lor y_1) \land (x_2 \lor y_2) \land \cdots \land (x_n \lor y_n)$$ which blows up to $2^n$ terms when converted to a DNF.

Most functions have CNF and DNF complexity very large – $\Theta(2^n/n)$ if I remember correctly – and so for random functions there is no blow-up for trivial reasons.

Miltersen, Radhakrishnan and Wegener construct a monotone function which has an exponential gap.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35209

 Ask a Question

 Download Related Notes/Documents