Abstract
Non-deterministic read-once branching programs, also known as non-deterministic free binary decision diagrams (nFBDD), are a fundamental data structure in computer science for representing Boolean functions. In this paper, we focus on #nFBDD, the problem of model counting for non-deterministic read-once branching programs. The #nFBDD problem is #P-hard, and it is known that there exists a quasi-polynomial randomized approximation scheme for #nFBDD. In this paper, we provide the first FPRAS for #nFBDD. Our result relies on the introduction of new analysis techniques that focus on bounding the dependence of samples.
Introduction
Model counting—the task of determining how many assignments satisfy a Boolean formula—is a cornerstone of artificial intelligence and database theory. However, it is computationally "hard" (#P-complete). To manage this, researchers use Knowledge Compilation, where complex formulas are translated into specialized data structures that make certain queries easier.
One such structure is the nFBDD (non-deterministic Free Binary Decision Diagram). These are "read-once," meaning each variable is checked at most once on any path, and "non-deterministic," meaning they can contain "guess" nodes (logical ORs). While nFBDDs are exponentially more compact (succinct) than their ordered counterparts (nOBDDs), they are much harder to count. Until now, only "quasi-polynomial" algorithms existed for #nFBDD, which are significantly slower than the polynomial-time algorithms (FPRAS) desired for practical scalability.
Methodology: The approxMCnFBDD Algorithm
The authors propose an algorithm called approxMCnFBDD that operates bottom-up through the branching program, calculating an estimate of the model count at each node. For each node $q$, the algorithm maintains a value $p(q)$ (an estimate of the inverse of the model count) and a set of samples.
The core innovation lies in how the algorithm handles non-determinism and sample dependence. To ensure the estimate is robust against outliers, it uses a "median of means" approach, partitioning samples into batches, averaging them, and then taking the median.
Embracing Sample Dependence
Standard approximation schemes usually require independent samples to bound variance. However, in nFBDDs, the lack of a fixed variable order makes independence computationally expensive to maintain. The authors allow samples to be dependent and introduce a new mathematical framework to bound this dependence.
They define a "canonical" derivation path for every satisfying assignment. By analyzing where these paths diverge (the "last common prefix node"), they can quantify the correlation between samples and prove that the variance remains manageable. This structural analysis is a powerful technique that could potentially be applied to other complex data structures like Decomposable Negation Normal Forms (DNNFs).
Results and Complexity
As a theoretical computer science paper, the evaluation consists of rigorous mathematical proofs demonstrating that the algorithm meets the criteria for an FPRAS. The authors formally prove that approxMCnFBDD is a valid FPRAS for #nFBDD, running in polynomial time relative to the input size, $1/\epsilon$, and $\log(1/\delta)$.
The algorithm runs in time $O(n^{11} |B|^{10} \epsilon^{-4} \log(\delta^{-1}))$, where $n$ is the number of variables and $|B|$ is the size of the branching program. This result resolves a significant gap in the knowledge compilation map, showing that #nFBDD is indeed approximable in polynomial time.
Limitations and Future Work
While the algorithm is technically polynomial, the exponents (e.g., $|B|^{10}$) are quite high. In its current form, the algorithm is a "proof of concept" for polynomial complexity rather than a tool ready for immediate industrial deployment.
A promising direction for future work is to improve the complexity (reduce the exponents) to enable practical adoption in database engines or AI model counters. Additionally, researchers may explore if these "dependence-bounding" techniques can be extended to even more expressive languages, such as general DNNFs or multilinear programs.
Summary updated