---
title: "A Tractable Class of Abduction Problems"
authors:
  - "Kave Eshghi"
doi: ""
url: "https://ijcai.org/proceedings/1993/1"
pdf: "https://ijcai.org/proceedings/1993/0001.pdf"
venue: "Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence"
year: 1993
pages: "3-7"
track: "Automated Reasoning"
keywords:
---

# A Tractable Class of Abduction Problems

Kave Eshghi

*Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence*, pages 3-7.

## Abstract

The problem of fmding a set of assumptions which explain a given proposition is in general NP-hard, even when the background theory is an acyclic Hom theory. In this paper it is shown that when the background theory is acyclic Hom and its pseudo-completion is unit refutable, there is a polynomial time algorithm for fmding minimal explanations. A test for unit-refutability of clausal theories is presented, based on the topology of the connection graph of the theory.