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
