The Compilability Thresholds of 2-CNF to OBDD

Alexis de Colnet, Alfons Laarman, Joon Hyung Lee

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,\delta n)$, the uniform distribution…