On the hardness of approximate reasoning

被引:328
作者
Roth, D
机构
[1] Aiken Compulation Laboratory, Harvard University, Cambridge, MA 02138
关键词
D O I
10.1016/0004-3702(94)00092-1
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Many AI problems, when formalized, reduce to evaluating the probability that a propositional expression is true. In this paper we show that this problem is computationally intractable even in surprisingly restricted cases and even if we settle for an approximation to this probability. We consider various methods used in approximate reasoning such as computing degree of belief and Bayesian belief networks, as well as reasoning techniques such as constraint satisfaction and knowledge compilation, that use approximation to avoid computational difficulties, and reduce them to model-counting problems over a propositional domain. We prove that counting satisfying assignments of propositional languages is intractable even for Horn and monotone formulae, and even when the size of clauses and number of occurrences of the variables are extremely limited. This should be contrasted with the case of deductive reasoning, where Horn theories and theories with binary clauses are distinguished by the existence of linear time satisfiability algorithms. What is even more surprising is that, as we show, even approximating the number of satisfying assignments (i.e., ''approximating'' approximate reasoning),is intractable for most of these restricted theories. We also identify some restricted classes of propositional formulae for which efficient algorithms for counting satisfying assignments can be given.
引用
收藏
页码:273 / 302
页数:30
相关论文
共 39 条
  • [1] [Anonymous], 1989, INTELLIGENT DECISION
  • [2] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
  • [3] BACCHUS F, 1992, P 10 NAT C ART INT A, P602
  • [4] BACCHUS F, 1990, REPRESENTING REASONI
  • [5] CARNAP R, 1950, LOGICAL F PROBABILIT
  • [6] THE COMPUTATIONAL-COMPLEXITY OF PROBABILISTIC INFERENCE USING BAYESIAN BELIEF NETWORKS
    COOPER, GF
    [J]. ARTIFICIAL INTELLIGENCE, 1990, 42 (2-3) : 393 - 405
  • [7] APPROXIMATING PROBABILISTIC INFERENCE IN BAYESIAN BELIEF NETWORKS IS NP-HARD
    DAGUM, P
    LUBY, M
    [J]. ARTIFICIAL INTELLIGENCE, 1993, 60 (01) : 141 - 153
  • [8] STRUCTURE IDENTIFICATION IN RELATIONAL DATA
    DECHTER, R
    PEARL, J
    [J]. ARTIFICIAL INTELLIGENCE, 1992, 58 (1-3) : 237 - 270
  • [9] Dechter R., 1988, ARTIF INTELL, P370, DOI DOI 10.1016/0004-3702(87)90002-6
  • [10] GREINER R, 1992, PRINCIPLES OF KNOWLEDGE REPRESENTATION AND REASONING: PROCEEDINGS OF THE THIRD INTERNATIONAL CONFERENCE (KR 92), P383