1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Shaull May 21 at 18:17
  • $\begingroup$ Sure, a formula halfway between CNF and DNF will blow up both ways, but I would like to characterize the worst case more precisely. $\endgroup$ – salvalcantara May 21 at 19:33
  • $\begingroup$ How do you measure the size of a CNF/DNF? $\endgroup$ – Yuval Filmus May 21 at 20:28
  • $\begingroup$ 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. $\endgroup$ – salvalcantara May 22 at 2:49
  • $\begingroup$ 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. $\endgroup$ – salvalcantara May 22 at 3:14
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks Yuval, you nailed it down. If my understanding is correct, a monotone formula does not contain NOTs, so this case helps to lower the upper bound for the size. $\endgroup$ – salvalcantara May 22 at 3:49
  • $\begingroup$ In the monotone case, NOTs don’t help to reduce the size of CNF/DNF. $\endgroup$ – Yuval Filmus May 22 at 6:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.