# Worst simultaneous blowup when converting to CNF and DNF

I know that converting between CNF and DNF produces an exponential blowup in size, but I would like to know which is the bound in size for a converted formula when one can choose between any of the two normal forms. Or, stated otherwise, given the predicate $$p$$, how to find:

$$\rho = \max \min \left\{\alpha, \beta\right\}$$

where

$$\alpha = \mathcal{O}(\text{CNF}(p))$$

$$\beta = \mathcal{O}(\text{DNF}(p))$$

• Do you want to know how to compute this bound, or how big it can get in general? For the latter, you can just take a formula that is partially in CNF and partially in DNF, so it blows up both ways. May 21, 2020 at 18:17
• Sure, a formula halfway between CNF and DNF will blow up both ways, but I would like to characterize the worst case more precisely. May 21, 2020 at 19:33
• How do you measure the size of a CNF/DNF? May 21, 2020 at 20:28
• I guess size would correspond to the number of "groups" (clauses or terms). Another option would be to count the total number of literals. Yet another option, these two options could be combined, and define size as the average size of "groups" (clauses or terms), where the size of a group would be the number of literals on it. Whatever measure captures the complexity of a formula in a better way, I am not sure what that measure is, so I left it open in my question. May 22, 2020 at 2:49
• Expanding a bit on the size, one could also consider the size of a formula to be the number of operators (and, or, not) on it, since that corresponds to the required number of logical gates in a hardware implementation. May 22, 2020 at 3:14

The worst example is parity. Any CNF/DNF for parity must contain $$2^{n-1}$$ terms of size $$n$$. In contrast, this answer on cstheory shows that every CNF/DNF contains at most $$2^{n-1}$$ terms.
In the monotone case, the worst example is Majority. Majority has $$\binom{n}{\lfloor n/2 \rfloor}$$ many minterms/maxterms (for odd $$n$$), each of size $$\lceil n/2 \rceil$$. Since the set of minterms/maxterms is an antichain, by Sperner's theorem it contains at most $$\binom{n}{\lceil n/2 \rceil}$$ many minterms/maxterms. Moreover, the LYM inequality easily implies that the maximum total size of sets in an antichain is $$\lceil n/2 \rceil \binom{n}{\lceil n/2 \rceil}$$, exactly matching the performance of Majority.