TL;DR
This paper resolves an open problem in knowledge compilation and theoretical computer science by presenting the first Fully Polynomial-Time Randomized Approximation Scheme (FPRAS) for counting the models of non-deterministic read-once branching programs (#nFBDD). The core breakthrough is a novel bottom-up sampling algorithm that abandons sample independence, proving that bounded dependence along canonical "derivation paths" suffices to control estimator variance.
What Problem Does This Paper Address?
Model counting—computing the number of satisfying assignments of a Boolean function—is a foundational problem across artificial intelligence, probabilistic databases, and formal verification. The general problem is $\#\text{P}$-hard. To make queries tractable, knowledge compilation compiles functions into restricted graph representations.
For ordered non-deterministic branching programs (nOBDD), a breakthrough in 2019 proved an FPRAS exists using the self-reducibility union property. However, free non-deterministic branching programs (nFBDD), also known as read-once non-deterministic branching programs (1-NBP), allow variables to appear in different orders along different paths. This makes them exponentially more succinct than nOBDDs, but breaks self-reducibility. Previously, only quasi-polynomial-time approximation schemes were known for #nFBDD. This paper tackles the question: Can we approximate #nFBDD in fully polynomial time?
Methods
The paper develops an algorithm called approxMCnFBDD that operates bottom-up on an alternating, 1-complete, 0-reduced nFBDD DAG:
- Bottom-up Probability Tracking and Sampling: For each node $q$, the algorithm tracks a value $p(q) \approx |\text{mod}(q)|^{-1}$ alongside $n_s \cdot n_t$ sample sets $S^r(q) \subseteq \text{mod}(q)$.
- Decision Nodes ($\text{ite}(x, q_1, q_0)$): Probabilities are combined via parallel sum $p(q) = (p(q_0)^{-1} + p(q_1)^{-1})^{-1}$, and sample sets are subsampled ("reduced") with appropriate ratios.
- Disjunction Nodes ($\lor$): Multiple paths can represent the same assignment. The algorithm ensures each model is counted exactly once by assigning it uniquely to the first child branch that satisfies it.
- Median-of-Means Estimator: The algorithm partitions $N = n_s \cdot n_t$ sample sets into $n_t$ batches of size $n_s$, computing batch means to tame variance and taking the median to boost confidence.
- Proof via Coupling and a Parallel Random Process: Because intermediate sampling probabilities are themselves random variables, standard induction breaks down. The authors define a coupling with an idealized random process over possible "histories" to rigorously analyze conditional probabilities.
Datasets
Not discussed in the paper. As a purely theoretical algorithms paper, no empirical datasets or benchmarks were used.
Key Insights and Ideas
- Embracing Dependence: Prior FPRAS designs for nOBDD relied heavily on producing independent samples. Because branches in nFBDD share subgraphs under different variable orders, achieving full independence was deemed impossible in polynomial time. The authors show that samples do not need to be independent, or even pairwise independent, to construct a low-variance estimator.
- Canonical Derivation Paths: To analyze the correlation between two assignments $\alpha, \alpha'$, each model is mapped to a unique canonical path from the terminal sink to the node.
- Bounding Pairwise Collision: The probability that both $\alpha$ and $\alpha'$ appear in sample set $S^r(q)$ depends inversely on the value $p(q^*)$ at their last common prefix node $q^*$ (where their derivation paths diverge): $$\Pr[\alpha \in S^r(q) \mid \alpha' \in S^r(q)] \le \frac{p(q)}{p(q^*)}$$
- Controlled Divergence: Crucially, the number of assignment pairs diverging at any specific node $q^*$ is geometrically bounded by $\frac{|\text{mod}(q)|^2}{|\text{mod}(q^*)|}$. This ensures that summing over all possible divergence points keeps the estimator variance within a constant factor of the square of the mean ($O(\mu^2)$), allowing Chebyshev's inequality and median-of-means to succeed.
Key Results
- First FPRAS for #nFBDD (Theorem 1): Given an nFBDD $B$ over $n$ variables, precision $\varepsilon > 0$, and error tolerance $\delta > 0$,
approxMCnFBDDreturns an estimate $\text{est}$ satisfying: $$\Pr\left[\text{est} \in (1 \pm \varepsilon)|B^{-1}(1)|\right] \ge 1 - \delta$$ - Complexity: The algorithm runs in deterministic polynomial time: $$O\left(n^5 \varepsilon^{-4} \log(\delta^{-1}) |B|^6 \log |B|\right)$$ proving that approximate model counting for nFBDD is polynomial in input size, $1/\varepsilon$, and $\log(1/\delta)$.
Limitations and Future Work
- High Polynomial Degree: The theoretical time complexity has an exponent of $O(n^5 |B|^6 \varepsilon^{-4})$, which is currently too high for practical implementation on large industrial circuits.
- Beyond nFBDD: The authors leave as an open challenge whether their "bounded dependence along derivation paths" technique can be extended to even richer knowledge compilation languages that generalize nFBDDs, such as general Decomposable Negation Normal Forms (DNNFs).
- Proof Simplification: The authors note that the coupling argument over execution histories is intricate, and finding a simplified analysis framework remains an inviting open problem.
Summary updated