Abstract | ||
---|---|---|
The problem of abduction can be characterized as finding the best explanation ofa set of data. In this paper we focus on one type of abduction in which the bestexplanation is the most plausible combination of hypotheses that explains all thedata. We then present several computational complexity results demonstratingthat this type of abduction is intractable (NP-hard) in general. In particular,choosing between incompatible hypotheses, reasoning about cancellation effectsamong... |
Year | DOI | Venue |
---|---|---|
1991 | 10.1016/0004-3702(91)90005-5 | Artif. Intell. |
Keywords | Field | DocType |
computational complexity | Knowledge representation and reasoning,Artificial intelligence,Machine learning,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
49 | 1-3 | 0004-3702 |
Citations | PageRank | References |
158 | 13.89 | 18 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tom Bylander | 1 | 993 | 139.38 |
Dean Allemang | 2 | 421 | 69.42 |
Michael C. Tanner | 3 | 331 | 52.98 |
John R. Josephson | 4 | 1003 | 119.16 |