The complexity of logic-based abduction

ABSTRACT

Abduction is an important form of nonmonotonic reasoning allowing one to find explanations for certain symptoms or manifestations. When the application domain is described by a logical theory, we speak about logic-based abduction. Candidates for abductive explanations are usually subjected to minimality criteria such as subset-minimality, minimal cardinality, minimal weight, or minimality under prioritization of individual hypotheses. This paper presents a comprehensive complexity analysis of relevant decision and search problems related to abduction on propositional theories. Our results indicate that abduction is harder than deduction. In particular, we show that with the most basic forms of abduction the relevant decision problems are complete for complexity classes at the second level of the polynomial hierarchy, while the use of prioritization raises the complexity to the third level in certain cases.

REFERENCES

• 1: ~ALLEMANG, D., TANNER, M. C., BYLANDER, T., AND JOSEPHSON, J. 1987. Computational com- ~plexity of hypothesis assembly. In Proceedings of the 1987 International Joint Conference on ~Artificial Intelligence. Morgan-Kaufmann, San Mateo, Calif., pp. 112-117.
• 2: Alselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth, Occam's razor, Information Processing Letters, v.24 n.6, p.377-380, 6 April 1987 [doi>10.1016/0020-0190(87)90114-1]
• 3: Gerhard Brewka, Nonmonotonic reasoning: logical foundations of common sense, Cambridge University Press, New York, NY, 1991
• 4: ~BYLANDER, T. 1991. The monotonic abduction problem: A functional characterization on the ~edge of tractability. In Proceedings KR-91. Morgan-Kaufmann, San Mateo, Calif., pp. 70- 77.
• 5: Tom Bylander , Dean Allemang , Michael C. Tanner , John R. Josephson, Some results concerning the computational complexity of abduction, Proceedings of the first international conference on Principles of knowledge representation and reasoning, p.44-54, December 1989
• 6: Tom Bylander , Dean Allemang , Michael C. Tanner , John R. Josephson, The computational complexity of abduction, Artificial Intelligence, v.49 n.1-3, p.25-60, May 1991 [doi>10.1016/0004-3702(91)90005-5]
• 7: ~CADOLI, M., AND SCHAERF, M. 1993. A survey on complexity results for non-monotonic logics. ~Tech. rep. Dipartimento di Informatica e Sistemistica, Universith di Roma "La Sapienza". ~Rome, Italy. J. Logic Prog. 17, 127-160.
• 8: ~CADOLI, M., AND SCHAERF, M. 1992. Approximate inference for concept languages. In Proceed- ~ings KR-92. Morgan-Kaufmann, San Mateo, Calif., pp. 330-341.
• 9: ~CHARNIAK, E. 1986. A neat theory of marker passing. In ProceedingsAAAI-86, pp. 584-588.
• 10: E. Charniak, Motivation analysis, abductive unification, and nonmonotonic equality, Artificial Intelligence, v.34 n.3, p.275-295, April 1988 [doi>10.1016/0004-3702(88)90063-X]
• 11: Eugene Charniak , Drew McDermott, Introduction to artificial intelligence, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 12: ~CHEN, Z.-Z. AND TODA, S. 1991. On the complexity of computing optimal solutions. Int. J. ~ound. Comput. Sci. 2, 3, 207-220.
• 13: ~CONSOLE, L., THESE1DER DUPR~, D.. AND TORASSO, P. 1989. A theory of diagnosis for incom- ~plete causal models. In Proceedings of the 1989 International Joint Conference on Artifictal ~Intelhgence. Morgan-Kaufmann, San Mateo, Calif., pp. 1131-1137.
• 14: ~CONSOLE, L., THESEIDER DUPR~, B., AND TORASSO, P. 1991. On the relationship between ~abduction and deduction. J. Logic Comput. 1, 5, 661-690.
• 15: Luca Console , Pietro Torasso, A spectrum of logical definitions of model-based diagnosis, Computational Intelligence, v.7 n.3, p.133-141, Aug. 1991 [doi>10.1111/j.1467-8640.1991.tb00388.x]
• 16: Gregory F. Cooper, The computational complexity of probabilistic inference using Bayesian belief networks (research note), Artificial Intelligence, v.42 n.2-3, p.393-405, March 1990 [doi>10.1016/0004-3702(90)90060-D]
• 17: ~COX, P., AND PIETRZYKOWSKI, T. 1987. General diagnosis by abductive inference. In IEEE ~Symposium on Logic Programming. pp. 183-189.
• 18: Johan de Kleer, An assumption-based TMS, Artificial Intelligence, v.28 n.2, p.127-162, March 1986 [doi>10.1016/0004-3702(86)90080-9]
• 19: ~BOWLING, W., AND GALLIER, J.H. 1984. Linear-time algorithms for testing the satisfiability of ~propositional horn theories. J. Logic Prog. 3, 267-284.
• 20: ~DOYLE, J. 1979. A truth-maintenance system. Artif. Int. 12, 231-272.
• 21: Thomas Eiter , Georg Gottlob, Propositional circumscription and extended closed-world reasoning are &Pgr;p2-complete, Theoretical Computer Science, v.114 n.2, p.231-245, June 21, 1993 [doi>10.1016/0304-3975(93)90073-3]
• 22: Thomas Eiter , Georg Gottlob, On the complexity of propositional knowledge base revision, updates, and counterfactuals, Artificial Intelligence, v.57 n.2-3, p.227-270, Oct. 1992 [doi>10.1016/0004-3702(92)90018-S]
• 23: ~ESHGHI, K. 1988. Abductive planning with event calculus. In Proceedings of the 5th Interna- ~tional Conference and Symposium on Logic Programming. MIT Press, Cambridge, Mass., pp. ~562-579.
• 24: ~ESHOHI, K. 1993. A tractable class of abduction problems. In Proceedings of the 1993 Interna- tional Joint Conference on Artificial Intelligence. Morgan-Kaufmann, San Mateo, Calif., pp. 3-8.
• 25: Ronald Fagin , Jeffrey D. Ullman , Moshe Y. Vardi, On the semantics of updates in databases, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588100]
• 26: Stephen A. Fenner , Steven Homer , Mitsunori Ogiwara , Alan L. Selman, On Using Oracles That Compute Values, Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, p.398-407, February 25-27, 1993
• 27: J. J. Finger, Exploiting constraints in design synthesis, Stanford University, Stanford, CA, 1987
• 28: Gerhard Friedrich , Georg Gottlob , Wolfgang Nejdl, Hypothesis classification, abductive diagnosis and therapy, Proceedings of the international workshop on Expert systems in engineering : Principles and applications: Principles and applications, p.69-78, September 1990, Vienna, Austria
• 29: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 30: M I Ginsberg , M L Ginsberg, Counterfactuals, Artificial Intelligence, v.30 n.1, p.35-80, Oct. 1986 [doi>10.1016/0004-3702(86)90067-6]
• 31: ~GIORDANO, L., AND MARTELLI, A. 1990. An abductive characterization of the TMS. In Proceed- ~ings of ECAI-90. pp. 308-313.
• 32: ~GOTTLOB, G. 1992. Complexity results for nonmonotonic logics. J. Logic Comput. 2, 3 (June), ~397-425.
• 33: ~HARTSHORNE, C., ET AL., EDS. 1958. The Collected Papers of Charles Sanders Peirce, Cambridge ~Press, 1931-1958, Vol. II, pp. 272-607.
• 34: Jerry R. Hobbs , Mark Stickel , Paul Martin , Douglas Edwards, Interpretation as abduction, Proceedings of the 26th annual meeting on Association for Computational Linguistics, p.95-103, June 07-10, 1988, Buffalo, New York [doi>10.3115/982023.982035]
• 35: ~JOHNSON, D.S. 1990. A catalog of complexity classes. In Handbook of Theoretical Computer ~Science, vol. A, chap. 2. Elsevier Science Publishers B.V. (North-Holland), Amsterdam, The ~Netherlands. Also: Artif. Int. 63 (1993), 69-142.
• 36: ~JOSEPHSON, J., CHANDRASEKARAN, B., SMITH, J. J. W., AND TANNER, M. 1987. A mechanism for ~forming composite explanatory hypotheses. IEEE Trans. Systems, Man, and Cybernetics SMC-17, ~445-454.
• 37: ~KADIN, J. 1989. pNP{O(log ,ol and sparse turing-complete sets for NP. J. Comput. Syst. Sci. 39, ~282-298.
• 38: A. C. Kakas , P. Mancarella, Database updates through abduction, Proceedings of the sixteenth international conference on Very large databases, p.650-661, September 1990, Brisbane, Australia
• 39: ~KANN, V. 1992. On the approximability of NP-complete optimization problems. Ph.D. disserta- ~tion. Department of Numerical Analysis and Computing Science, Royal Institute of Technology, ~Stockholm, Sweden, May.
• 40: Kurt Konolige, Abduction versus closure in causal theories, Artificial Intelligence, v.53 n.2-3, p.255-272, Feb. 1992 [doi>10.1016/0004-3702(92)90073-7]
• 41: Elias Koutsoupias , Christos H. Papadimitriou, On the greedy algorithm for satisfiability, Information Processing Letters, v.43 n.1, p.53-55, Aug. 10, 1992 [doi>10.1016/0020-0190(92)90029-U]
• 42: ~KOW~SKI, R. 1991. Logic programs in artificial intelligence. In Proceedings of the 1991 ~International Joint Conference on Artificial Intelligence, Morgan-Kaufmann, San Mateo, Calif., pp. ~596-601.
• 43: Mark W. Krentel, The complexity of optimization problems, Journal of Computer and System Sciences, v.36 n.3, p.490-509, June 1988 [doi>10.1016/0022-0000(88)90039-6]
• 44: Mark W. Krentel, Generalizations of Opt P to the polynomial hierarchy, Theoretical Computer Science, v.97 n.2, p.183-198, April 27, 1992 [doi>10.1016/0304-3975(92)90073-O]
• 45: ~LEVESQUE, H. 1989. A knowledge-level account for abduction. In Proceedings of the 1989 ~International Joint Conference on Artificial Intelligence. MorgamKaufmann, San Mateo, Calif., pp. ~1061-1067.
• 46: ~LIFSCHITZ, V. 1985. Computing circumscription. In Proceedings of the 1985 bzternational Joint ~onference on Artificial Intelligence. Morgan-Kaufmann, San Mateo, Calif., pp. 121-127.
• 47: ~MAREK, W., AND TRUSZCZYIqSKI, M. 1990. Modal logic for default reasoning. Ann. Math. Artif. ~Int. 1,275-302.
• 48: Drew McDermott, Nonmonotonic Logic II: Nonmonotonic Modal Theories, Journal of the ACM (JACM), v.29 n.1, p.33-57, Jan. 1982 [doi>10.1145/322290.322293]
• 49: ~MCDERMOTT, D., AND DOYLE, J. 1980. Non-monotonic logic I. Artif. Int. 13, 41-72.
• 50: ~MEYER, m., AND STOCKMEYER, L. 1972. The equivalence problem for regular expressions with ~squaring requires exponential time. In Proceedings of the 13th Annual Symposium on Swttehing ~and Automata Theory. IEEE Computer Society, New York, pp. 125-129.
• 51: Robert C. Moore, Semantical considerations on nonmonotonic logic, Artificial Intelligence, v.25 n.1, p.75-94, Jan. 1985 [doi>10.1016/0004-3702(85)90042-6]
• 52: MORGAN, C.G. 1971. Hypothesis generation by machine. Artif. Int. 2, 179-187.
• 53: ~NEBEL, B. 1991. Belief revision and default reasoning: Syntax-based approaches. In Proceed- ~ings KR-91. pp. 417-428.
• 54: ~NORVIG, P. 1987. Inference in text understanding. In Proceedings AAAI-87. Morgan-Kauf- ~mann, San Mateo, Calif., pp. 561-565.
• 55: Christos H. Papadimitriou , Martha Sideri, On Finding Extensions of Default Theories, Proceedings of the 4th International Conference on Database Theory, p.276-281, October 14-16, 1992
• 56: J Pearl, Fusion, propagation, and structuring in belief networks, Artificial Intelligence, v.29 n.3, p.241-288, Sept. 1986 [doi>10.1016/0004-3702(86)90072-X]
• 57: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 58: ~PEmCE, C.S. 1955. Abduction and induction. In Philosophical Writings of Peirce, chapter 11. J. ~Buchler, ed. Dover, New York.
• 59: Yun Peng , James A. Reggia, Abductive inference models for diagnostic problem-solving, Springer-Verlag New York, Inc., New York, NY, 1990
• 60: David Poole, A logical framework for default reasoning, Artificial Intelligence, v.36 n.1, p.27-47, August 1988 [doi>10.1016/0004-3702(88)90077-X]
• 61: ~POOLE, D. 1989a. A methodology for using a default and abductive reasoning system. Int. J. ~Int. Syst. 5, 5, 521-548.
• 62: D. Poole, Explanation and prediction: an architecture for default and abductive reasoning, Computational Intelligence, v.5 n.2, p.97-110, May 1989 [doi>10.1111/j.1467-8640.1989.tb00319.x]
• 63: ~POOLE, D. 1989C. Normality and faults in logic based diagnosis. In Proceedings of the 1989 ~b~ternational Joint Conference on Artificial b~telhgence. Morgan-Kaufmann, San Mateo, Calif., pp. ~1304-1310.
• 64: ~POPLE, H. 1973. On the mechanization of abductive logic. In Proceedings of the 1973 bztema- ~tional Joint Conference on Artifictal hztelligence. Morgan-Kaufmann, San Mateo, Calif., pp. ~147-152.
• 65: ~PROVAN, G. 1990. The computational complexity of multiple-context truth maintenance sys- ~tems. In Proceedings ECAI-90, (Aug). pp. 522-527.
• 66: RE~TER, R. 1980. A logic for default reasoning. Artif. Int. 13, 81-132.
• 67: R Reiter, A theory of diagnosis from first principles, Artificial Intelligence, v.32 n.1, p.57-95, April 1987 [doi>10.1016/0004-3702(87)90062-2]
• 68: Vladislav Rutenburg, Complexity classification of truth maintenance systems, Proceedings of the 8th annual symposium on Theoretical aspects of computer science, p.372-383, February 1991, Hamburg, Germany
• 69: ~SELMAN, B., AND LEVESQUE, H.J. 1990. Abductive and default reasoning: A computational ~core. In Proceedings AAAI-90, (July). pp. 343-348.
• 70: ~SELMAN, B., LEVESQUE, H. J., AND MITCHELL, D. 1992. A new method for solving hard ~satisfiability problems. In Proceedings AAAI-92 (July). pp. 440-446.
• 71: ~STILLMAN, J. 1992. The complexity of propositional default logic. In Proceedings AAAI-92 ~(July). pp. 794-799.
• 72: L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]
• 73: K. W. Wagner, More complicated questions about maxima and minima, and some closures of NP, Theoretical Computer Science, v.51 n.1-2, p.53-80, March 31, 1987 [doi>10.1016/0304-3975(87)90049-1]
• 74: Klaus W. Wagner, Bounded query classes, SIAM Journal on Computing, v.19 n.5, p.833-846, Oct. 1990 [doi>10.1137/0219058]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Theory

Keywords:
abduction, complexity analysis, diagnosis, propositional logic, reasoning