A Proofs omitted from the paper

Using the procedure given in Proposition 2 (in Section A.2), For the proofs in this section, we will use the following notation. Without any loss of generality we assume the latter. 's are i.i.d random variables taking values in [0, 1], we apply the Chernoff bound to find For CNFs, testing satisfiability is known to be NP-hard. For DNFs, deciding validity is known to be co-NP-hard. From the fact that d -DNNF s support weighted counting and sampling we have the existence results.