In Answer Set Programming (ASP), the ability to reason about what is not known—known as negation-as-failure—is a cornerstone of its expressive power. However, this power comes at a computational cost. Simple ASP programs, which lack negation and disjunction, are significantly easier to solve but are restricted in the types of problems they can represent.
Recent research explores a surprising alternative: instead of adding complex logical operators to a single program, we can achieve the same expressive power by allowing multiple simple programs to communicate with one another.
The Limits of Simple Logic
A "simple" ASP program consists only of definite rules. These programs are monotonic; adding new information can only ever increase the set of facts we know to be true. While efficient, they cannot express non-monotonic reasoning, such as "if there is no evidence of a flight delay, assume the plane will land on time."
To handle such cases, standard ASP uses negation-as-failure (NAF). NAF allows a program to conclude something based on the absence of information. In Communicating Answer Set Programs, Kim Bauters et al. investigate whether this specific logical construct is strictly necessary, or if it can be replaced by a different mechanism: inter-program communication.
Communication as a Logical Operator
The core intuition behind this research is that the result of a query to another program can serve as a proxy for a logical operator.
Imagine two simple programs, $P_1$ and $P_2$. If $P_1$ can ask $P_2$, "Do you have a valid answer set?" the answer to that question provides information that $P_1$ does not possess locally. If $P_2$ fails to find a solution, $P_1$ can use that failure as a signal. In this way, the act of querying another program effectively simulates negation.
Kim Bauters et al. demonstrate that this mechanism allows a system of communicating simple programs to reach the same expressive power as a single normal ASP program containing negation-as-failure. This means that distributed reasoning can compensate for the absence of complex logical constructs within individual components.
Bridging the Expressiveness Gap
The impact of communication depends heavily on the protocol used. The authors distinguish between different levels of communication complexity:
- Simple Communication: By allowing programs to query each other, even programs that are individually "weak" (NP-easy) can collectively solve NP-hard problems.
- Focused Communication: In Communicating Answer Set Programs, the authors introduce a "focused" mechanism. This allows simple programs to simulate not just negation, but also disjunction (the "OR" operator), which further elevates the system's complexity.
- Multi-focused Communication: In Expressiveness of communication in answer set programming, Kim Bauters et al. show that more sophisticated interfaces allow these systems to capture the entire polynomial hierarchy, reaching as far as PSPACE.
Why Communication Boosts Complexity
Why does talking to another program make a system so much more powerful? The answer lies in how communication interacts with the search space.
When a program queries another, it is essentially performing a sub-computation. If the query is "does an answer set exist?", the responding program must explore its own search space. The calling program then branches its own logic based on that result. This nesting of searches—where one program's execution depends on the success or failure of another's search—is what allows the combined system to tackle problems of much higher complexity than any single component could handle alone.
As argued by Kim Bauters et al., the design of the communication interface itself can be a greater source of computational capability than the inherent logic of the individual programs. This shifts the focus of ASP research from making individual solvers more complex to designing more effective ways for simple solvers to cooperate.
Key Foundational Work
Communicating Answer Set Programs (2010) — contributed 10 concept elements to this direction.
Expressiveness of communication in answer set programming (2011) — contributed 8 concept elements to this direction.