THE COMPUTATIONAL-COMPLEXITY OF ABDUCTION

被引：180
作者：
BYLANDER, T
ALLEMANG, D
TANNER, MC
JOSEPHSON, JR
机构：
[1] Laboratory for Artificial Intelligence Research, Department of Computer and Information Science, The Ohio State University, Columbus
来源：
ARTIFICIAL INTELLIGENCE | 1991年 / 49卷 / 1-3期
关键词：
D O I：
10.1016/0004-3702(91)90005-5
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
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.
引用
收藏
页码：25 / 60
页数：36
相关论文
共 33 条
  • [1] ALLEMANG D, 1987, P 10 INT JOINT C ART, P1112
  • [2] BYLANDER T, 1989, 1ST P INT C PRINC KN, P44
  • [3] Charniak E., 1985, INTRO ARTIFICIAL INT
  • [4] THE COMPUTATIONAL-COMPLEXITY OF PROBABILISTIC INFERENCE USING BAYESIAN BELIEF NETWORKS
    COOPER, GF
    [J]. ARTIFICIAL INTELLIGENCE, 1990, 42 (2-3) : 393 - 405
  • [5] DAVIS R, 1988, EXPLORING ARTIFICIAL, P297
  • [6] DIAGNOSING MULTIPLE FAULTS
    DEKLEER, J
    WILLIAMS, BC
    [J]. ARTIFICIAL INTELLIGENCE, 1987, 32 (01) : 97 - 130
  • [7] DEKLEER J, 1989, P IJCAI 89 DETROIT, P1324
  • [8] DVORAK D, 1989, P 11 INT JOINT C ART, P1238
  • [9] ESHELMAN L, 1988, AUTOMATING KNOWLEDGE, P37
  • [10] Garey MR., 1979, COMPUTERS INTRACTABI
1234