L NNF DNNF d-DNNF FBDD OBDD OBDD< DNF CNF PI IP MODS sd-DNNF
NNF ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤
DNNF 6≤∗ ≤ ≤ ≤ ≤ ≤ ≤ 6≤∗ ≤ ≤ ≤
d-DNNF 6≤∗ ≤ ≤ ≤ ≤ 6≤∗ ≤ ≤
FBDD 6≤ 6≤ 6≤ ≤ ≤ ≤
OBDD 6≤ 6≤ 6≤ 6≤ ≤ ≤
OBDD< 6≤ 6≤ 6≤ 6≤ 6≤ ≤
DNF 6≤ 6≤ 6≤ 6≤ 6≤ 6≤ ≤ 6≤ 6≤ ≤ ≤ CNF 6≤ 6≤ 6≤ 6≤ 6≤ 6≤ 6≤ ≤ ≤ 6≤
PI 6≤ 6≤ 6≤ 6≤ 6≤ 6≤ 6≤ 6≤ ≤ 6≤ IP 6≤ 6≤ 6≤ 6≤ 6≤ 6≤ 6≤ 6≤ 6≤ ≤
MODS ≤
sd-DNNF 6≤∗ 6≤∗ ≤ ≤

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

Table 13:
digraph represented by I contains a k-clique of a special kind (k **is a parameter of the family). It is**
shown that for certain values of k (depending on n**), every FBDD representation of Σ has exponential**
size. Moreover, it is shown that Σ has only a cubic number of prime implicants. This shows that FBDD 6≤ IP**, hence** FBDD 6≤ DNF**. Because** FBDD satisfies ¬C (see Proposition 5.1),8**it cannot be the**
case that ¬**Σ has a polynomial size** FBDD. Since ¬**Σ has only a cubic number of prime implicates, we**
obtain that FBDD 6≤ PI**, hence** FBDD 6≤ CNF**. The remaining results in this table follow since** FBDD≤ OBDD ≤ OBDD<.

Table 14: **Assume that** d-DNNF ≤ DNF **holds. As a consequence, every sentence Σ in** DNF **can be**
compiled into an equivalent d-DNNF sentence Σ∗ **of polynomial size. Now, checking whether a clause**
γ **is entailed by the** CNF **sentence Σ is equivalent to checking whether the** DNF **sentence** ¬Σ ∨ γ is valid. Checking whether (¬Σ)∗∨γ is valid—when (¬Σ)∗ **is a** d-DNNF sentence and γ **is a clause—can**
be achieved in polynomial time by Lemma A.11. Therefore, (¬Σ)∗ **is a polysize compilation of the**
8. That is, a sentence in FBDD **can be negated in polytime to yield a sentence in** FBDD **too.**

L NNF DNNF d-DNNF FBDD OBDD OBDD< DNF CNF PI IP MODS sd-DNNF
NNF ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤
DNNF 6≤∗ ≤ ≤ ≤ ≤ ≤ ≤ 6≤∗ ≤ ≤ ≤
d-DNNF 6≤∗ 6≤∗ ≤ ≤ ≤ ≤ 6≤∗ 6≤∗ ≤ ≤
FBDD 6≤ 6≤ 6≤ ≤ ≤ ≤ 6≤ 6≤ 6≤ 6≤ 6≤ ![0_image_3.png](0_image_3.png)

![0_image_2.png](0_image_2.png)

