Abstract
A model of computation that is widely used in the formal analysis of reactive systems is symbolic algorithms. In this model, the access to the input graph is restricted to symbolic operations, which are expensive in comparison to standard RAM operations. This paper establishes the first unconditional lower bounds for symbolic graph algorithms, proving that fundamental tasks like finding strongly connected components (SCCs) or checking safety properties require at least $\Omega(n)$ operations. These lower bounds reveal a significant separation between these problems and the reachability problem, which can be solved in $O(D)$ operations, where $D$ is the graph diameter. Additionally, the authors present a novel $(1+\epsilon)$-approximation algorithm for the graph diameter and provide a refined analysis of existing SCC algorithms.
The Symbolic Model and the Reachability Paradox
In the formal analysis of reactive systems (such as microprocessors or flight controllers), the state space is often astronomical. Symbolic algorithms handle this by manipulating sets of states using operations like Binary Decision Diagrams (BDDs) rather than individual vertices. The primary computational cost is measured in "symbolic steps"—operations like finding the predecessors or successors of a set.
For decades, a "Reachability Paradox" has been observed: while reachability (can I get from A to B?) takes $O(D)$ steps, its dual problem, Safety (do I always stay in a good set?), appeared to take $O(n)$ steps. This research proves that this gap is inherent and unavoidable, even for graphs with constant diameter.
Key Results: The Complexity Gap
The paper provides a definitive table of bounds for symbolic operations. The most striking finding is that while Reachability depends on the diameter ($D$), problems like SCC, Safety, and Liveness depend on the number of vertices ($n$).
Furthermore, the authors show that the state-of-the-art SCC algorithm by Gentilini et al. is actually optimal, with a complexity proportional to the sum of the diameters of the individual strongly connected components.
Methodology: Communication Complexity
To prove these lower bounds, the authors link symbolic computation to Communication Complexity. They use a reduction from the Set Disjointness problem, a well-known problem where two parties must determine if their sets share elements using minimal communication. By constructing specific "gadget" graphs where symbolic operations can be simulated with few bits of communication, they demonstrate that a sub-linear symbolic algorithm would contradict established communication complexity limits.
Approximating Graph Diameter
While exact diameter computation is shown to require $\Omega(n)$ steps, the paper introduces a new approximation strategy. The authors found that a $(1 + \epsilon)$-approximation can be achieved much faster than the naive $O(n \cdot D)$ approach by using a greedy "dominating set" strategy adapted for symbolic sets.
This new algorithm achieves a $(1 + \epsilon)$-approximation in $\tilde{O}(n\sqrt{D})$ symbolic steps, bridging the gap between the efficient 2-approximation and the costly exact calculation.
Conclusion
This work provides a theoretical breakthrough by establishing the fundamental limits of symbolic algorithms. By proving linear lower bounds for safety and SCC problems, it justifies the observed performance of existing verification tools. Future research may focus on closing the remaining gaps in diameter approximation thresholds and exploring the impact of BDD size on these complexity bounds.
Summary updated