Introduction
Answer Set Programming (ASP) is a powerful declarative framework for knowledge representation and solving hard combinatorial problems. While "normal" ASP is NP-complete, the addition of disjunctions (e.g., $a \lor b \leftarrow \text{body}$) significantly increases its expressive power, pushing the complexity to $\Sigma^P_2$-completeness. This paper, presented at AAAI-24, investigates whether structural properties of a program can be exploited to find "shortcuts" through this complexity, specifically asking if we can avoid the dreaded "double-exponential" runtime wall.
Structural Parameters and ASP
In the field of parameterized complexity, researchers seek to identify parameters $k$ that capture the "thinness" of a problem's structure. If a problem can be solved in time exponential only to $k$ (e.g., $2^k$), it is considered more manageable than one requiring double-exponential time ($2^{2^k}$). Common structural measures include treewidth, vertex cover, and feedback vertex set.
As illustrated in Figure 5, the structure of an ASP program can be analyzed through different lenses. The dependency graph (left) captures interactions between atoms, while the incidence graph (right) maps atoms to the specific rules in which they appear. These representations are fundamental for defining the structural parameters that the authors evaluate to determine if they can tame disjunctive complexity.
The Vertex Cover Boundary
The authors identify Vertex Cover (VC) size—a restrictive measure of how many "hub" atoms are needed to touch every rule—as a critical boundary for tractability. They prove that for disjunctive ASP with bounded rule sizes, a polynomial kernel exists. This allows a large program to be "shrunk" into a smaller version whose size depends only on the VC, enabling a single-exponential solving time. This result provides a rare positive case where structure successfully mitigates the inherent hardness of disjunction.
The Double-Exponential "No-Go" Theorems
For most other popular structural measures, the results are less optimistic. The authors demonstrate that disjunction acts as a "structural cloaking device," allowing complex logical dependencies to be hidden within seemingly simple graph structures.
Even when parameters like treewidth (shown in Figure 3) or feedback vertex set are small, disjunctive ASP remains double-exponentially hard. Using a novel "logarithmic compression" technique, the authors show that a normal ASP program can be transformed into a disjunctive one while significantly reducing its structural parameter. This implies that unless the Exponential Time Hypothesis (ETH) is false, a single-exponential algorithm is impossible for a wide range of parameters between Vertex Cover and Treewidth, including treedepth, pathwidth, and cliquewidth.
Key Insights and Conclusion
The core insight of the paper is a fundamental trade-off: one can trade logical complexity for structural simplicity. By moving from normal to disjunctive logic, the underlying graph structure can be simplified while preserving the problem's inherent difficulty.
The paper establishes that Vertex Cover is a unique "sweet spot" for structural tractability in disjunctive ASP. Beyond this boundary, the "saturation" property of ASP allows disjunctions to simulate universal quantification, making the problem inherently harder than its normal counterparts. These findings have significant implications for the development of future ASP solvers and suggest new directions for research in fields like Neuro-symbolic AI, where efficient reasoning over complex logical structures is paramount.
Summary updated