Introduction
Calculating the probability that a complex logical statement is true—a problem known as Probabilistic Satisfiability (PSAT)—is fundamental across diverse fields, from engineering network reliability to statistical physics. Despite its importance, PSAT is computationally "nightmarish," belonging to the complexity class #P. This makes exact solutions or even accurate approximations for large, heterogeneous systems notoriously difficult to obtain. Standard methods often produce approximations that violate basic logical constraints, such as predicting probabilities outside the [0, 1] interval.
This paper introduces a novel framework designed specifically for monotonic problems—those where increasing the probability of individual events (e.g., more working links in a network) never decreases the overall probability of the system's success. By combining physics-inspired perturbative expansions with Bezier polynomial interpolation, the authors provide tight, guaranteed bounds that respect the fundamental properties of probability.
Methodology: Bridging the Gap with Bezier Interpolation
The proposed multi-stage approach leverages the behavior of the system at its extremes to infer its state in the complex transition region.
- Perturbative Expansions: The framework utilizes "weak-coupling" expansions (around the point where all event probabilities are 0) and "strong-coupling" expansions (around the point where all are 1).
- Bernstein Basis Representation: A key innovation is transforming these Taylor expansions into the Bernstein basis. Unlike standard power series, Bezier polynomials naturally respect "unitarity" (staying between 0 and 1) and monotonicity, ensuring the approximation remains physically and logically sound.
- Interpolation and Heterogeneity Mapping: To handle systems where events have different probabilities, the authors introduce a mapping using $\lambda$ (average location) and $\epsilon$ (heterogeneity envelope). This allows heterogeneous systems to be treated as perturbations of a simpler, uniform case.
Key Insights: Duality and the "Squeeze" Effect
The framework's power comes from two main conceptual pillars. First, the authors leverage the relationship between "struts" (paths that make a statement true) and "cuts" (sets of failures that make it false). This duality allows information from the low-probability end of the curve (cuts) to inform the high-probability end (struts).
Second, the "Squeeze" effect addresses the failure of single Taylor expansions in rapid transition regions. By combining expansions from both ends and applying monotonicity constraints, the method "squeezes" the error from both sides, creating a narrow band of possible values. When middle coefficients are unknown, a "structureless" assumption provides a principled interpolant.
Results: Accuracy and Tight Bounds
The method was evaluated using analytical benchmarks, such as a 7-event logical expression, and synthetic heterogeneous instances. The results demonstrate that Bezier interpolation significantly outperforms truncated Taylor series, which often diverge or violate the [0, 1] probability interval.
The framework produces "tight" upper and lower bounds, meaning there exists at least one valid problem instance matching those bounds. Furthermore, the error is controllable via parameters $S$ (sample size) and $D$ (expansion depth), allowing for a flexible trade-off between computational cost and accuracy.
Limitations and Future Directions
While highly effective for monotonic logic, extending this framework to general, non-monotonic problems remains a challenge. Additionally, the propagation of sampling uncertainty when minimal clauses are unknown requires further investigation. Future work may explore "step-wise renormalization" to further simplify calculations for massive systems.
Summary updated