The Compilability Thresholds of 2-CNF to OBDD
This work addresses a theoretical problem in computational complexity and knowledge compilation, providing precise thresholds that align with known properties like satisfiability and treewidth, but it is incremental as it builds on existing threshold results.
The paper tackles the problem of compilability thresholds for random 2-CNF formulas to OBDDs, showing that with high probability, formulas admit polynomial-size OBDDs for δ < 1/2 or δ > 1, but only exponential-size OBDDs for 1/2 < δ < 1.
We prove the existence of two thresholds regarding the compilability of random 2-CNF formulas to OBDDs. The formulas are drawn from $\mathcal{F}_2(n,δn)$, the uniform distribution over all 2-CNFs with $δn$ clauses and $n$ variables, with $δ\geq 0$ a constant. We show that, with high probability, the random 2-CNF admits OBDDs of size polynomial in $n$ if $0 \leq δ< 1/2$ or if $δ> 1$. On the other hand, for $1/2 < δ< 1$, with high probability, the random $2$-CNF admits only OBDDs of size exponential in $n$. It is no coincidence that the two ``compilability thresholds'' are $δ= 1/2$ and $δ= 1$. Both are known thresholds for other CNF properties, namely, $δ= 1$ is the satisfiability threshold for 2-CNF while $δ= 1/2$ is the treewidth threshold, i.e., the point where the treewidth of the primal graph jumps from constant to linear in $n$ with high probability.