

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

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

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

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

NNF ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤
DNNF ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤
d-DNNF ≤ ≤ ≤ ≤ ≤ ≤
FBDD ≤ ≤ ≤
OBDD ≤ ≤
OBDD< ≤
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 ≤ ≤
L NNF DNNF d-DNNF FBDD OBDD OBDD< DNF CNF PI IP MODS sd-DNNF
NNF ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤
DNNF ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤
d-DNNF ≤ ≤ ≤ ≤ ≤ ≤

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

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 ≤ ≤
Table 11:
formulas having exponentially many prime implicates. Subsequently IP 6≤ DNF and PI 6≤ CNF**. The**
remaining results in this table follow from the transitivity of ≤.

Table 10: **The parity function** On =Ln−1 i=0 xi has linear size OBDD< **representations (Bryant,**
1986) but only exponential size CNF and DNF representations. The reason is that On **has 2**n essential prime implicants (resp. essential prime implicates) and the number of essential prime implicants (resp. essential prime implicates) of a formula is a lower bound of the size of any of its DNF (resp. CNF) representation. This easily shows that both CNF 6≤ OBDD and DNF 6≤ OBDD**. The**
remaining results in this table follow from the language inclusions reported in Figure 4.

Table 11: **It is shown in (Darwiche, 2001b) that there is a sentence in** d-DNNF **which only**
has exponential FBDD **representations. Accordingly, we have** FBDD 6≤ d-DNNF**. In (Gergov & Meinel,**
1994a), it is shown that OBDD 6≤ FBDD**. Finally, it is easy to show that** OBDD< 6≤ OBDD **(for instance,**
the formula Σn =Vn i=1(xi ⇔ yi**) has an** OBDD< representation of size polynomial in n **whenever** <
satisfies x1 < y1 < x2 < ... < xn < yn**, while it has an** OBDD< **representation of size exponential in**
n provided that < is s.t. x1 < x2 < ... < xn < y1 < y2 < ... < yn**). The remaining results in this**
table follow from the language inclusions reported in Figure 4.

Table 12: L' 6≤∗ L means that L' 6≤ L unless the polynomial hierarchy PH **collapses. The**
results in this table follow since the existence of polysize knowledge compilation functions for clausal entailment implies the collapse of the polynomial hierarchy PH **(Selman & Kautz, 1996; Cadoli &**
Donini, 1997). Now, if DNNF ≤ CNF**, then for each sentence Σ in** CNF **there exists a polysize equivalent**
sentence Γ in DNNF**. Therefore, we can test whether a clause is entailed by Σ in polytime by testing**
whether the clause is entailed by Γ. This proves the existence of polysize knowledge compilation functions for clausal entailment, leading to the collapse of the polynomial hierarchy PH**. The same**
is true for d-DNNF and sd-DNNF **since all these languages support a polytime clausal entailment test**
(see Proposition 4.1).

Table 13: **In (Wegener, 1987) (Theorem 6.2 pp. 436), a family of** n 2**-variable boolean functions**
Σ is pointed out. Provided that every interpretation I **over these** n 2 variables represents a n**-vertices**
digraph (for every 1 ≤ i, j ≤ n, we have I(xi,j ) = 1 iff (i,j) is an arc of the digraph), Σ(I**) = 1 iff the**