Worst simultaneous blowup when converting to CNF and DNF

Question

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)) $$

Answer 1

You haven't explained how you measure the size of a CNF/DNF – two common options are number of clauses/terms and total size of the clauses/terms.

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.