Introduction
Answer-Set Programming (ASP) has emerged as a premier paradigm for solving complex combinatorial search and optimization problems. As a declarative logic programming language, ASP allows users to describe what a problem is rather than how to solve it. However, as ASP programs incorporate increasingly sophisticated features—such as aggregates and choice rules—the ability for a human user to trace the reasoning behind a specific result has diminished.
This paper, originally presented at IJCAI-23, addresses this transparency gap. The authors introduce a formal framework for explaining ASP results through the lens of Abstract Constraint Atoms (c-atoms), providing a theoretical foundation for building interactive tools that help users understand why certain facts are—or are not—present in a solution.
The Challenge: Beyond Basic Logic
While ASP is inherently more transparent than "black-box" neural networks, it can still be opaque to the end-user. When a solver returns an answer set, a user might naturally ask: "Why is this specific atom true?" or "Why was this other atom excluded?"
Existing explanation methods work well for basic logic rules but struggle with advanced language features such as:
- Aggregates: e.g., "Is the sum of these values greater than 10?"
- Choice Rules: e.g., "Pick exactly one of these three options."
The authors utilize c-atoms as a mathematical umbrella to cover these features. The goal is to provide concise, sufficient, and coherent reasons for the truth or falsity of atoms in programs that use these complex constraints.
Methodology: Dual Justification Framework
The authors propose two complementary types of justifications to bridge the gap between mathematical logic and human intuition:
1. Model-based Justifications (m-justifications)
This is a semantic approach that identifies the smallest "partial model" (a set of facts known to be true or false) sufficient to force a c-atom to its current state. These justifications are governed by three core principles:
- Sufficiency: The reason must be enough to guarantee the outcome.
- Coherence: The reason cannot contradict the actual solution.
- Conciseness: No superfluous information is included, ensuring the explanation remains digestible.
2. Rule-based Justifications (r-justifications)
This is a syntactic, operational approach. It builds a "justification chain" that mimics how a human might trace a derivation. Unlike many existing methods that work "bottom-up" (from facts to conclusions), this approach works top-down. This is more aligned with how users query a system (e.g., "Explain X"), allowing the system to provide a direct path from the query to the underlying evidence.
Complexity and Feasibility
A significant portion of the research is dedicated to mapping the computational difficulty of finding these justifications. Using the Polynomial Hierarchy, the authors categorize tasks ranging from standard NP-complete problems to more complex $\Sigma^p_2$ levels.
Crucially, the authors identify that for convex c-atoms—the most common type used in practical applications—the problems often become much simpler, falling into polynomial time or NP. They demonstrate that computing these justifications is feasible in polynomial time if the system has access to an NP oracle, which is a standard assumption for modern ASP solver-based tools.
Key Insights
- Symmetry of Truth and Falsity: The framework treats the absence of an atom with the same rigor as its presence. Explaining why a rule failed to fire is often more useful for debugging than explaining why one did.
- The Elaboration Concept: The authors introduce "elaborated" r-justifications. This allows a complex, high-level explanation to be broken down into smaller, more digestible steps, which is essential for an interactive user interface.
- Bridging Syntax and Semantics: A key finding (Theorem 5) shows that for "normal" and "convex" programs, the rule-based and model-based views align perfectly. This means that for most common ASP programs, the operational explanation matches the underlying mathematical logic.
Conclusion and Future Work
The paper proves that for any atom in an answer set, a valid r-justification chain always exists. While the general problem of finding justifications can be computationally expensive for highly non-convex or disjunctive programs, the framework provides a robust path forward for the majority of real-world use cases.
Future work aims to integrate these formal notions into a fully-fledged, interactive explanatory system. Additionally, the authors plan to address contrastive explanations—answering "Why X instead of Y?"—to further align symbolic AI reasoning with human cognitive requirements.
Summary updated