Skip to main content
SpringerLink
Log in

On the computational cost of disjunctive logic programming: Propositional case

  • Published:
Annals of Mathematics and Artificial Intelligence Aims and scope Submit manuscript

Abstract

This paper addresses complexity issues for important problems arising with disjunctive logic programming. In particular, the complexity of deciding whether a disjunctive logic program is consistent is investigated for a variety of well-known semantics, as well as the complexity of deciding whether a propositional formula is satisfied by all models according to a given semantics. We concentrate on finite propositional disjunctive programs with as well as without integrity constraints, i.e., clauses with empty heads; the problems are located in appropriate slots of the polynomial hierarchy. In particular, we show that the consistency check is Σ p2 -complete for the disjunctive stable model semantics (in the total as well as partial version), the iterated closed world assumption, and the perfect model semantics, and we show that the inference problem for these semantics is Π p2 -complete; analogous results are derived for the answer sets semantics of extended disjunctive logic programs. Besides, we generalize previously derived complexity results for the generalized closed world assumption and other more sophisticated variants of the closed world assumption. Furthermore, we use the close ties between the logic programming framework and other nonmonotonic formalisms to provide new complexity results for disjunctive default theories and disjunctive autoepistemic literal theories.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. K. Apt and H. Blair, Arithmetic classification of perfect models of stratified programs,Proc. ICLP/SLP-5 (MIT Press, 1988) pp. 766–779.

  2. K. Apt, H. Blair and A. Walker, Towards a theory of declarative knowledge, in Minker [44](, pp. 89–148.

    Google Scholar 

  3. C. Baral, J. Lobo and J. Minker, Generalized disjunctive well-founded semantics for logic programs: Declarative semantics,Proc. ISMIS-4, 1990, pp. 465–473.

  4. R. Ben-Eliyahu and R. Dechter, Propositional semantics for disjunctive logic programs,Proc. ICLP/SLP-7, 1992, pp. 813–827. Full paper in Ann. of Math. and Artificial Intelligence 12 (1994) 53–87.

  5. N. Bidoit and C. Froidevaux, General logic databases and programs: Default semantics and stratification, Inf. and Comput. 19 (1991) 15–54.

    Google Scholar 

  6. N. Bidoit and C. Froidevaux, Negation by default and unstratifiable programs, Theor. Comp. Sci. 78 (1991) 85–112.

    Google Scholar 

  7. H. Blair and C. Cholak, The complexity of local stratification, Technical Report, School of Computer and Information Sciences, Syracuse University (1992). To appear in Fund. Informaticae.

  8. H. Blair, W. Marek, A. Nerode, and J. Remmel (editors),Informal Proceedings of the Workshop on Structural Complexity and Recursion-Theoretic Methods in Logic Programming, Washington DC, November 1992 (Cornell University, Mathematical Sciences Institute).

  9. H. Blair, W. Marek and J. Schlipf, The expressiveness of locally stratified programs, Technical Report 92-8, Mathematical Sciences Institute, Cornell University (1992). Ann. of Math. and Artificial Intelligence 15 (1995) 209–229.

    Google Scholar 

  10. M. Cadoli, The complexity of model checking for circumscriptive formulae, Inf. Processing Lett. 44 (1992) 113–118.

    Google Scholar 

  11. M. Cadoli and M. Lenzerini, The complexity of closed world reasoning and circumscription, J. Comp. and Syst. Sci. 43 (1994) 165–211.

    Google Scholar 

  12. M. Cadoli and M. Schaerf, A survey of complexity results for non-monotonic logics, J. Logic Programming 17 (1993) 127–160.

    Google Scholar 

  13. E. Chan, A possible worlds semantics for disjunctive databases, IEEE Trans. Data and Knowledge Eng. 5(2) (1993) 282–292.

    Google Scholar 

  14. A. Chandra and D. Harel, Horn clause queries and generalizations, J. Logic Programming 2 (1985) 1–15.

    Google Scholar 

  15. R. Chang and P. Rohatgi, On unique satisfiability and randomized reductions, Bull. EATCS 47 (1990) 151–159.

    Google Scholar 

  16. J. Chomicki and V.S. Subrahmanian, Generalized closed world assumption is Π 02 -complete, Inf. Processing Lett. 34 (1990) 289–291.

    Google Scholar 

  17. J. Dix and M. Müller, Abstract properties and computational complexity of semantics for disjunctive logic programs, in Blair et al. [8], pp. 15–28.

  18. J. Dix and M. Müller, Implementing semantics of disjunctive logic programs using fringes and abstract properties,Proc. LPNMR-2 (MIT Press, 1993) pp. 43–59.

  19. T. Eiter and G. Gottlob, Reasoning with parsimonious and moderately grounded expansions, Fund. Informaticae 17(1,2) (1992) 31–53.

    Google Scholar 

  20. T. Eiter and G. Gottlob, Complexity results for disjunctive logic programming and application to nonmonotonic logics,Proc. ILPS-10 (MIT Press, 1993) pp. 266–278.

  21. T. Eiter and G. Gottlob, Propositional circumscription and extended closed world reasoning are Π p2 -complete, Theor. Comp. Sci. 114(2) (1993) 231–245. Addendum 118:315.

    Google Scholar 

  22. J. Fernández and J. Minker, Semantics of disjunctive deductive databases,Proc. ICDT-4 (Springer, 1992) pp. 21–50.

  23. M. Garey and D.S. Johnson,Computers and Intractability — A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).

    Google Scholar 

  24. M. Gelfond and V. Lifschitz, The stable model semantics for logic programming,Proc. ILPS-5 (MIT Press, 1988) pp. 1070–1080.

  25. M. Gelfond and V. Lifschitz, Classical negation in logic programs and disjunctive databases, New Generation Comput. 9 (1991) 365–385.

    Google Scholar 

  26. M. Gelfond and H. Przymusinska, Negation as failure: careful closure procedure, Artificial Intelligence 30 (1986) 273–287.

    Google Scholar 

  27. M. Gelfond, H. Przymusinska, V. Lifschitz and M. Truszczyński, Disjunctive defaults,Proc. KR-2, 1991, pp. 230–237.

  28. M. Gelfond, H. Przymusinska and T. Przymusinski, On the relationship between circumscription and negation as failure, Artificial Intelligence 38 (1989) 75–94.

    Google Scholar 

  29. G. Gottlob, Complexity results for nonmonotonic logics, J. Logic Comput. 2(3) (1992) 397–425.

    Google Scholar 

  30. D.S. Johnson, A catalog of complexity classes, in J. van Leeuwen, editor,Handbook of Theoretical Computer Science, Vol. A (Elsevier Science Publ., 1990) chap. 2.

  31. H. Kautz and B. Selman, Hard problems for simple default logics, Artificial Intelligence 49 (1991) 243–279.

    Google Scholar 

  32. V. Lifschitz, Computing circumscription,Proc. IJCAI-9, 1985, pp. 121–127.

  33. V. Lifschitz and G. Schwarz, Extended logic programs as autoepistemic theories,Proc. LPNMR-2 (MIT Press, 1993) pp. 101–114.

  34. J. Lobo, J. Minker and A. Rajasekar,Foundations of Disjunctive Logic Programming (MIT Press, Cambridge, MA, 1992).

    Google Scholar 

  35. W. Marek, A. Nerode and J. Remmel, A theory of nonmonotonic rule systems II, Ann. of Math. and Artificial Intelligence 5 (1992) 229–264.

    Google Scholar 

  36. W. Marek, A. Nerode and J. Remmel, How complicated is the set of stable models of a recursive logic program? Ann. Pure and Appl. Logic 56 (1992) 119.

    Google Scholar 

  37. W. Marek, A. Rajasekar and M. Truszczyński, Complexity of computing with extended propositional logic programs, in Blair et al. [8], pp. 93–102.

  38. W. Marek and M. Truszczyński, Autoepistemic logic, J. ACM 38(3) (1991) 588–619.

    Google Scholar 

  39. W. Marek and M. Truszczyński, Computing intersection of autoepistemic expansions, in Nerode et al. [46], pp. 37–50.

  40. W. Marek and M. Truszczyński, Reflexive autoepistemic logic and logic programming,Proc. LPNMR-2 (MIT Press, 1993) pp. 115–131.

  41. J. McCarthy, Circumscription — a form of non-monotonic reasoning, Artificial Intelligence 13 (1980) 27–39.

    Google Scholar 

  42. J. McCarthy, Applications of circumscription to formalizing common-sense knowledge, Artificial Intelligence 28 (1986) 89–116.

    Google Scholar 

  43. J. Minker, On indefinite data bases and the closed world assumption,Proc. CADE-6, 1982, pp. 292–308.

  44. J. Minker, (editor)Foundations of Deductive Databases and Logic Programming (Morgan Kaufman, Washington DC, 1988).

    Google Scholar 

  45. R. Moore, Semantical considerations on nonmonotonic logics, Artificial Intelligence 25 (1985) 75–94.

    Google Scholar 

  46. A. Nerode, W. Marek and V.S. Subrahmanian (editors),Proc. LPNMR-1 (MIT Press, 1991).

  47. I. Niemelä, Towards automatic reasoning,Proc. Europ. Workshop on Logics in AI, Amsterdam, September 1990, LNCS # 478 (Springer, 1991).

  48. T. Przymusinski, On the declarative and procedural semantics of stratified deductive databases, in Minker [44](, pp. 193–216.

    Google Scholar 

  49. T. Przymusinski, Stable semantics for disjunctive programs, New Generation Comput. 9 (1991) 401–424.

    Google Scholar 

  50. T. Przymusinski, Three-valued nonmonotonic formalisms and semantics of logic programming, Artificial Intelligence 49 (1991) 309–344.

    Google Scholar 

  51. A. Rajasekar, J. Lobo and J. Minker, Weak generalized closed world assumption, J. Autom. Reasoning 5 (1989) 293–307.

    Google Scholar 

  52. R. Reiter, On closed-world databases, in H. Gallaire and J. Minker (editors)Logic and Data Bases (Plenum Press, New York, 1978) pp. 55–76.

    Google Scholar 

  53. R. Reiter, A logic for default reasoning, Artificial Intelligence 13 (1980) 81–132.

    Google Scholar 

  54. K. Ross, The well-founded semantics for disjunctive logic programs,Proc. DOOD-1, 1989, pp. 352–369.

  55. K. Ross and R. Topor, Inferring negative information from disjunctive databases, J. Autom. Reasoning 4(2) (1988) 397–424.

    Google Scholar 

  56. Ch. Sakama, Possible model semantics for disjunctive databases,Proc. DOOD-1, 1989, pp. 337–351.

  57. M. Schaerf, Logic programming and autoepistemic logics: new relations and complexity results,Proc. Italian AI Conference (IA *AI), 1993, Springer LNCS/AI #728.

  58. J.S. Schlipf, The expressive powers of logic programming semantics, Technical Report CIS-TR-90-3, Computer Science Department, University of Cincinnati (1990). Preliminary version inProc. PODS-90, pp. 196–204. To appear in J. Comp. and Syst. Sci.

  59. J.S. Schlipf, A survey of complexity and undecidability results in logic programming, in Blair et al. [8], pp. 93–102.

  60. J.S. Schlipf., When is closed world reasoning tractable?,Proc. ISMIS-3 (Elsevier Science Publ., 1998) pp. 485–494.

  61. G. Schwarz, Autoepistemic logic of knowledge, in Nerode et al. [46], pp. 260–274.

  62. J. Stillman, The complexity of propositional default logic,Proc. AAAI-10, 1992, pp. 794–799.

  63. L. Stockmeyer and A. Meyer, Word problems requiring exponential time,Proc. STOC-5 (ACM, 1973) pp. 1–9.

  64. A. Van Gelder, Negation as failure using tight derivations for general logic programs, in Minker [44](, pp. 1149–1176.

    Google Scholar 

  65. A. Van Gelder, K. Ross and J.S. Schlipf, The well-founded semantics for general logic programs, J. ACM 38(3) (1991) 620–650.

    Google Scholar 

  66. K. Wagner, Bounded query classes, SIAM J. Comp. 19(5) (1990) 833–846.

    Google Scholar 

  67. A. Yahya and L. Henschen, Deduction in non-Horn databases, J. Autom. Reasoning 1(2) (1985) 141–160.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Christian Doppler Laboratory for Expert Systems, Institut für Informationssysteme, Technische Universität Wien, Paniglgasse 16, A-1040, Wien, Austria

    Thomas Eiter & Georg Gottlob

Authors
  1. Thomas Eiter
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Georg Gottlob
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Parts of the results in this paper appeared in form of an abstract in the Proceedings of the Twelfth ACM SIGACT SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-93), pp. 158–167. Other parts appeared in shortened form in the Proceedings of the International Logic Programming Symposium, Vancouver, October 1993 (ILPS-93), pp. 266–278. MIT Press.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Eiter, T., Gottlob, G. On the computational cost of disjunctive logic programming: Propositional case. Ann Math Artif Intell 15, 289–323 (1995). https://doi.org/10.1007/BF01536399

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01536399

Keywords

Search

Navigation