The Asymmetry of Deduction and Abduction
In classical logic, deduction and abduction are two sides of the same coin, yet they possess radically different computational profiles. Deduction is a forward-moving process: given a set of facts and rules, what else must be true? Abduction is the inverse: given an observation, what is the best set of hypotheses to explain it?
For decades, computer scientists optimized deductive reasoning by restricting knowledge bases to simplified logical fragments. The most famous of these is Horn logic (clauses with at most one positive literal), which reduces the complexity of deduction to linear time. However, as Hector J. Levesque pointed out in A Knowledge-Level Account of Abduction, traditional logic-based approaches to abduction remain globally intractable because they are inherently tied to the global properties of standard first-order logic.
This intractability is not a minor overhead; it is a fundamental barrier. As demonstrated by Bart Selman and Hector J. Levesque in Abductive and Default Reasoning: A Computational Core, restricting background knowledge to Horn clauses does not make abductive reasoning tractable. While verifying a deductive consequence takes linear time, selecting the right subset of supporting assumptions to explain an observation remains NP-hard.
Deduction follows a deterministic path forward, but abduction requires a goal-directed search through a combinatorial explosion of potential assumption subsets. The complexity is so deeply embedded that, as Selman et al. proved, the search process remains NP-hard even when a unique explanation is guaranteed. The difficulty is not driven by the volume of possible answers, but by the sheer hardness of choosing valid combinations of assumptions.
The Anatomy of Intractability
To understand why abduction resists standard computational optimizations, we must look at how constraints compound the problem. In a basic diagnostic setting, an agent might need to explain a single symptom. But real-world systems must explain multiple observations simultaneously.
This requirement introduces what B. Chandrasekaran 0001 termed abductive assembly in Towards a Functional Architecture for Intelligence Based on Generic Information Processing Tasks—the process of compounding individual hypotheses into a single, coherent explanation. Even when individual sub-tasks are optimized, assembling these pieces triggers a complexity explosion. Thomas Eiter and Kazuhisa Makino confirmed this in On Computing all Abductive Explanations, showing that finding a unified explanation for multiple distinct observations remains NP-complete even in highly simplified logical frameworks.
A common engineering response to NP-hard problems is preprocessing, or knowledge compilation. If the background theory and the list of possible assumptions are known in advance, can we pre-compute them into a structure that answers queries in polynomial time?
The answer, unfortunately, is generally negative. In Compilability of Abduction, the authors demonstrated that core abductive tasks—such as determining if a valid explanation exists, or if a specific assumption is relevant or necessary—remain computationally hard ($\Sigma^P_2$-hard) even after a polynomial-size preprocessing step. This hardness persists even when explanations are ordered by preference (such as minimality or length), proving that the complexity is fundamental to the abductive inference step itself.
[Background Theory + Hypotheses] ---> (Polynomial Preprocessing) ---> [Compiled Knowledge Base]
|
[New Observation] -----------------------> (Query Phase: Still Σp2-hard)
Could we bypass this by simply looking for small explanations? Michael R. Fellows et al. explored this via parameterized complexity in The Parameterized Complexity of Abduction. They discovered that bounding the size of the desired explanation within Horn logic still results in W[P]-complete complexity. Restricting the solution's brevity does not alleviate the structural intractability of the search space.
Breaking the Complexity Barrier
If propositional abduction is "almost always hard"—as Gustav Nordh and Bruno Zanuttini proved in Propositional Abduction is Almost Always Hard, noting it only yields to polynomial time under hyper-restrictive conditions like "affine relations of width 2"—how can practical AI systems function?
Researchers have found tractability by abandoning standard formula-based representations or by exploiting the topological structure of the knowledge base.
Shifting from Formulas to Models
Instead of representing knowledge as a collection of logical rules and searching backward through them, we can represent the knowledge base using a strategic subset of its satisfying assignments, known as characteristic models.
Henry A. Kautz et al. demonstrated the power of this paradigm shift in Reasoning With Characteristic Models. They proved that while finding minimal explanations is NP-complete in formula-based Horn logic, the problem becomes solvable in polynomial time when using characteristic models. By evaluating models directly, the system bypasses the combinatorial explosion of rule-based goal-directed search.
Exploiting Structural Topology
A second path to tractability relies on the graph-theoretic structure of the interactions between rules and hypotheses. Kave Eshghi identified a tractable class in A Tractable Class of Abduction Problems by focusing on acyclic Horn theories that pass a specific topological graph test.
Taking structural topology further, Georg Gottlob et al. leveraged database theory in Efficient Datalog Abduction through Bounded Treewidth. They proved that if the logical interaction graph has a bounded treewidth—meaning the graph behaves structurally like a tree without deeply nested, complex loops—abductive diagnosis becomes tractable.
In Abduction with Bounded Treewidth: From Theoretical Tractability to Practically Efficient Computation, the authors translated these bounded-treewidth problems into Monadic Datalog. This shift provided a concrete algorithmic path to linear-time, highly parallelizable abductive reasoning, bridging the gap between theoretical complexity and real-world diagnostic engines.
Alternative Paradigms and Continuous Spaces
As AI transitioned toward continuous representations, researchers looked for ways to map the discrete, combinatorial steps of abduction into continuous optimization problems.
- Energy Minimization: In A Potts Spin MFT Network Solving Multiple Causal Interactions, Lotfi Ben Romdhane 0001 bypassed discrete search entirely by mapping causal abduction onto a Potts spin network using Mean Field Theory (MFT). The discrete problem of selecting causes becomes a continuous energy-minimization problem, allowing neural dynamics to settle on optimal explanations.
- Tensor Algebra: To preserve symbolic precision while leveraging linear algebra, Yaniv Aspis et al. introduced a framework in Tensor-Based Abduction in Horn Propositional Programs. By encoding Horn programs into third-order tensors, they transformed the computationally difficult "backward" steps of abduction into a series of iterative matrix-tensor multiplications.
Symbolic Rules & Observations ---> Tensor Encoding (Third-Order Tensors) ---> Iterative Matrix Multiplications ---> Minimal Explanations
- Heuristic Coherence: In natural language processing, the search space is too vast for exact logical methods. Hwee Tou Ng and Raymond J. Mooney tackled this in On the Role of Coherence in Abductive Explanation by introducing explanatory coherence. Instead of minimizing the absolute number of assumptions (Occam's Razor), they prioritized explanations that maximize the connections between observations, dramatically pruning the search space.
- Embedding Similarity: For modern large-scale language models, evaluating abductive reasoning through fine-tuning is computationally expensive. Emils Kadikis et al. addressed this in Embarrassingly Simple Performance Prediction for Abductive Natural Language Inference. They demonstrated that the geometric similarity of sentence embeddings can predict how well a model will perform on abductive tasks. This approach operates hundreds of times faster than traditional evaluation methods, bypassing the underlying computational bottlenecks of abductive inference.
Key Foundational Work
A Knowledge-Level Account of Abduction (1989) — contributed 1 concept elements to this direction.
Towards a Functional Architecture for Intelligence Based on Generic Information Processing Tasks (1987) — contributed 1 concept elements to this direction.