Abductive and Default Reasoning: A Computational Core

Bart Selman, Hector J. LevesqueAAAI 1990 · OpenReview

Abstract

Of all the possible ways of computing abductive explanations, the Assumption-based Truth Maintenance System (ATMS) procedure is one of the most popular. While this procedure is known to run in exponential time in the worst case, the proof actually depends on the existence of queries with an exponential number of answers. This research explores whether the difficulty stems from returning large sets of explanations or if the task is inherently hard. By analyzing abduction tasks that return relatively small answers, we demonstrate that while generating some non-trivial explanations is fast, deciding if an explanation contains a specific hypothesis is NP-hard. Furthermore, we identify a shared "computational core" between abductive reasoning and Reiter’s default logic, establishing that the complexity of both forms of reasoning arises from the same underlying subtask.

Introduction

In the field of knowledge representation, abductive reasoning—the process of finding a set of assumptions (an explanation) to account for an observed fact—is a fundamental requirement for diagnostic and plan-recognition systems. Historically, the Assumption-based Truth Maintenance System (ATMS) served as the primary tool for this task. However, the ATMS was frequently criticized for its exponential runtime.

Researchers initially hypothesized that this inefficiency was a byproduct of the "output explosion" problem: the ATMS attempts to list every possible explanation, and in many logical systems, the number of explanations can be exponential relative to the size of the input. This paper investigates a deeper question: Is abduction computationally difficult only because we demand all answers, or is finding even a single, specific answer inherently hard?

The Support Selection Task

To analyze the complexity of these reasoning tasks, the authors focus on Horn theories, a restricted form of propositional logic. In Horn theories, standard deduction (determining what follows from a set of facts) is highly efficient, typically occurring in linear time. This makes Horn theories an ideal environment to isolate the complexity of abduction itself.

Central to this analysis is the definition of the Support Selection Task: given a set of facts and a target query, the system must find a set of assumptions that consistently explains the query. The authors utilize mathematical reductions—specifically mapping the "Path with Forbidden Pairs" problem from graph theory—to demonstrate the hardness of this task.

Key Insights: The Illusion of Simplicity

One of the most significant findings is that restricting a system to Horn clauses does not guarantee tractability for abduction. While deduction becomes easy, the process of choosing the correct assumptions to include remains a "computational monster."

The research reveals that the difficulty is driven by goal-direction. The authors prove that:

  1. Finding any random, non-trivial explanation is efficient ($O(kn)$).
  2. The problem becomes NP-hard the moment a constraint is added, such as requiring the explanation to include a specific hypothesis or restricting the explanation to a specific set of allowed assumption letters.
  3. Even if a problem is guaranteed to have only one unique explanation, finding that single answer remains NP-hard (under randomized reductions).

Bridging Abduction and Default Logic

A major contribution of this work is the discovery of a shared computational core between abduction and Default Logic. Default logic is used to make "rule-of-thumb" assumptions when information is incomplete. The authors show that abduction (finding a minimal set of assumptions to explain a fact) and default reasoning (finding a maximal set of conclusions, known as an extension) are two sides of the same coin.

Both processes rely on the same difficult Support Selection subtask. The paper proves that finding a specific extension in Reiter’s Default Logic is NP-hard, even for very simple "elementary" defaults and acyclic Horn theories. This establishes, for the first time, a formal connection between the computational difficulties of these two distinct reasoning frameworks.

Implications for AI Systems

These results provide a theoretical validation for the ATMS. The exponential behavior observed in such systems is not necessarily a result of poor algorithmic design, but rather a reflection of the fundamental hardness of the task. The research suggests that the method of listing all explanations, as employed by the ATMS, likely cannot be significantly improved upon for general cases.

For symbolic AI, this presents a challenge: unlike deduction, where one can often trade expressiveness for speed, abduction remains stubbornly difficult even in restricted logical forms.

Conclusion and Future Work

The findings suggest that the search for a fast, general-purpose abductive reasoner may be futile. Instead, the authors propose two potential paths for future research:

  1. Approximate Reasoning: Developing methods to find "good enough" or approximate explanations rather than exhaustive or perfect ones.
  2. Limited Abduction: Exploring principled forms of unsound or incomplete abduction, where a system might miss certain explanations to maintain computational feasibility.

By defining the boundaries of tractable reasoning, this work shifted the focus of the field toward understanding where complexity truly resides in automated inference.

Summary updated

Abstract

Of all the possible ways of computing abductive explanations, the ATMS procedure is one of the most popular. While this procedure is known to run in exponential time in the worst case, the proof actually depends on the existence of queries with an exponential number of answers. But how much of the difficulty stems from having to return these large sets of explanations? Here we explore abduction tasks similar to that of the ATMS, but which return relatively small answers. The main result is that although it is possible to generate some non-trivial explanations quickly, deciding if there is an explanation containing a given hypothesis is NP-hard, as is the task of generating even one explanation expressed in terms of a given set of assumption letters. Thus, the method of simply listing all explanations, as employed by the ATMS, probably cannot be improved upon. An interesting result of our analysis is the discovery of a subtask that is at the core of generating explanations, and is also at the core of generating extensions in Reiter's default logic. Moreover, it is this subtask that accounts for the computational difficulty of both forms of reasoning. This establishes for the first time a strong connection between computing abductive explanations and computing extensions in default logic.
BibTeX
@inproceedings{selman1990abductive,
  author = {Bart Selman and Hector J. Levesque},
  title = {{Abductive and Default Reasoning: A Computational Core}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1990},
  url = {https://openreview.net/forum?id=rklOZAg_bB},
}
Figure