The computational complexity of abduction
Artificial IntelligencePublished 1 May 1991
Tom Bylander, Dean Allemang, Michael C. Tanner, John R. Josephson
Citations413
SJR quartileQ1
SJR score1.84
SNIP3.30
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper focuses on one type of abduction in which the best explanation is the most plausible combination of hypotheses that explains all the data, and presents several computational complexity results demonstrating that thistype of abduction is intractable (NP-hard) in general.
Abstract
The problem of abduction can be characterized as finding the best explanation of a set of data. In this paper we focus on one type of abduction in which the best explanation is the most plausible combination of hypotheses that explains all the data. We then present several computational complexity results demonstrating that this type of abduction is intractable (NP-hard) in general. In particular, choosing between incompatible hypotheses, reasoning about cancellation effects among hypotheses, and satisfying the maximum plausibility requirement are major factors leading to intractability. We also identify a tractable, but restricted, class of abduction problems.
Keywords
Computer Science
Artificial IntelligenceA theory of diagnosis from first principles
2,897 Citations1987Raymond Reiter
The theory accommodates diagnostic reasoning in a wide variety of practical settings, including digital and analogue circuits, medicine, and database updates, and reveals close connections between diagnostic reasoning and nonmonotonic reasoning.
Artificial IntelligenceFusion, propagation, and structuring in belief networks
2,152 Citations1986Judea Pearl
SIAM Journal on ComputingThe Complexity of Enumeration and Reliability Problems
2,086 Citations1979Leslie G. Valiant
For a large number of natural counting problems for which there was no previous indication of intractability, that they belong to the class of computationally eqivalent counting problems that are at least as difficult as the NP-complete problems.
Artificial IntelligenceDiagnosing multiple faults
2,053 Citations1987Johan de Kleer, Brian C. Williams
The diagnostic procedure presented in this paper is model-based, inferring the behavior of the composite device from knowledge of the structure and function of the individual components comprising the device.
Artificial IntelligenceThe computational complexity of probabilistic inference using bayesian belief networks
1,935 Citations1990Gregory F. Cooper
It is shown that probabilistic inference using belief networks is NP-hard,Therefore, research should be directed away from the search for a general, efficient probabilism inference algorithm, and toward the design of efficient special-case, average- case, and approximation algorithms.
New England Journal of Medicine<i>Internist-I</i>, an Experimental Computer-Based Diagnostic Consultant for General Internal Medicine
1,103 Citations1982Randolph A. Miller, Harry E. Pople +1 more
It is demonstrated that the present form of the INTERNIST-I program is not sufficiently reliable for clinical applications and specific deficiencies that must be overcome include the program’s inability to reason anatomically or temporally, its inability to construct differential diagnoses spanning multiple problem areas, and its occasional attribution of findings to improper causes.
International Journal of Man-Machine StudiesDiagnostic expert systems based on a set covering model
393 Citations1983James A. Reggia, Dana Nau +1 more
It is proposed that a generalization of the set covering problem can be used as an intuitively plausible model for diagnostic problem solving and potentially useful as a basis for expert systems in that it provides a solution to the difficult problem of multiple simultaneous disorders.
International Joint Conference on Artificial IntelligenceDiagnosis with behavioral modes
357 Citations1989Johan de Kleer, Brian C. Williams
Elsevier eBooksModel-based Reasoning: Troubleshooting
275 Citations1988Randall Davis, Walter Hamscher
The current state of the art in model-based reasoning, particularly its application to diagnosis and troubleshooting, is surveyed, reviewing areas that are well understood and exploring areas that present challenging research topics.
Annals of Internal MedicineArtificial Intelligence in Medicine.
254 Citations1983
The feasibility of predicting the functional outcome for ischemic stroke patients and the usability of multimodal deep learning architectures for this purpose are demonstrated.
International Joint Conference on Artificial Intelligence“Physical Negation”—integrating fault models into the General Diagnostic Engine
240 Citations1989Peter Struß, Oskar Dressier
IEEE Transactions on Systems Man and CyberneticsA Probabilistic Causal Model for Diagnostic Problem Solving Part I: Integrating Symbolic Causal Inference with Numeric Probabilistic Inference
236 Citations1987Yun Peng, James A. Reggia
It is shown that the causal relationships in a general diagnostic domain can be used to remove the barriers to applying Bayesian classification effectively and provides insight into which notions of "parsimony" may be relevant in a given application area.
Computational IntelligenceExplanation and prediction: an architecture for default and abductive reasoning
212 Citations1989David Poole
This paper elaborates on the idea that reasoning should be viewed as theory formation where logic tells us the consequences of the authors' assumptions, and proposes an architecture to combine explanation and prediction into one coherent framework.
International Joint Conference on Artificial IntelligenceThe formation of composite hypotheses in diagnostic problem solving: an exercise in synthetic reasoning
211 Citations1977Harry E. Pople
Experience with the INTERNIST system suggests that many aspects of the search process could be significantly enhanced if it were possible to attend to the various component problems and their interrelationships simultaneously.
Artificial IntelligenceDistributed revision of composite beliefs
190 Citations1987Judea Pearl
The chapter demonstrates how numerical probabilities can be used as a catalyst for coherent transformations from evidence sentences to conclusion sentences and identifies the structures that allow such transformations to be executed by autonomous production rules and those that invite problems of intractability and instability unless treated with care.
Medical Entomology and ZoologyProceedings of the first international conference on Principles of knowledge representation and reasoning
189 Citations1989Ronald J. Brachman, Hector J. Levesque +1 more
Proceedings held May 1989 Topics include temporal logic, hierarchical knowledge bases, default theories, nonmonotonic and analogical reasoning, formal theories of belief revision, and metareasoning.
Model-based monitoring of dynamic systems
184 Citations1992Daniel Dvorak, Benjamin Kuipers
International Joint Conference on Artificial IntelligenceA knowledge-level account of abduction
148 Citations1989Hector J. Levesque
IEEE Transactions on Systems Man and CyberneticsA Mechanism for Forming Composite Explanatory Hypotheses
143 Citations1987John R. Josephson, B. Chandrasekaran +2 more
A general problem-solving mechanism is described that is especially suited for performing a particular form of abductive inference, or best explanation finding, and a problem solver embodying this mechanism synthesizes composite hypotheses by combining simple hypotheses to satisfy explanatory goals.
IEEE Transactions on Systems Man and CyberneticsA Probabilistic Causal Model for Diagnostic Problem Solving Part II: Diagnostic Strategy
135 Citations1987Yun Peng, James A. Reggia
A domain-independent algorithm is presented that uses symbolic causal knowledge and numeric probabilistic knowledge to generate and evaluate plausible hypotheses during diagnostic problem solving.
Kluwer international series in engineering and computer scienceMOLE: A Knowledge-Acquisition Tool for Cover-and-Differentiate Systems
109 Citations1988Larry J. Eshelman
By distinguishing between covering and differentiating knowledge and by using this distinction to help it refine the expert’s preferences, MOLE is able to disambiguate an under-specified knowledge base and to interactively refine an incomplete knowledge base.
Journal of Medical SystemsRED: A red-cell antibody identification expert module
39 Citations1985Jack W. Smith, John R. Svirbely +4 more
A software module in an expert system RED, which interprets data related to red cell antibody identification, is described, which combines the atomic hypotheses judged favorably by the antibody programs into a unified judgment concerning the case.