On the complexity of propositional knowledge base revision, updates, and counterfactuals

ABSTRACT

We study the complexity of several recently proposed methods for updating or revising propositional knowledge bases. In particular, we derive complexity results for the following problem: given a knowledge base T, an update p, and a formula q, decide whether q is derivable from Top, the updated (or revised) knowledge base. This problem amounts to evaluating the counterfactual p > q over T. Besides the general case, also subcases are considered, in particular where T is a conjunction of Horn clauses, or where the size of p is bounded by a constant.

REFERENCES

• 1: Krzysztof R. Apt, Introduction to Logic Programming, University of Texas at Austin, Austin, TX, 1988
• 2: A.a. Bonner. A Logic for Hypothetical Reasoning. In Proceedings AAAI-88, pages 480-484, 1988.
• 3: A. J. Bonner, Hypothetical datalog negation and linear recursion, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.286-300, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73750]
• 4: Alexander Borgida, Language features for flexible handling of exceptions in information systems, ACM Transactions on Database Systems (TODS), v.10 n.4, p.565-603, Dec. 1985 [doi>10.1145/4879.4995]
• 5: Genevieve Bossu , Pierre Siegel, Saturation, nonmonotonic reasoning and the closed-world assumption, Artificial Intelligence, v.25 n.1, p.13-63, Jan. 1985 [doi>10.1016/0004-3702(85)90040-2]
• 6: M. Cadoli and M. Lenzerini. The Complexity of Closed World Reasoning and Circumscription. In Proceedings AAAI-90, pages 550-555, 1990.
• 7: M. Dalal. Investigations into a Theory of Knowledge Base Revision: Preliminary Report. in Proceedings AAAI-88, pages 475--479, 1988.
• 8: M. Dalal. Updates in Propositional Databases. Technical Report DCS-TR-222, Rutgers University, Dept. of Computer Science, Feb. 1988.
• 9: 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]
• 10: W. DoMing and J. H. Gallier. Linear-time Algorithms for Testing the Satisfiability of Propositional Horn Theories. Journal of Logic Programming, 3:267-284, 1984.
• 11: T. Eiter and G. Gottlob. On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals. Technical Report CD/TR 91-23, Christian Doppler Laboratory for Expert Systems, Vienna University of Technology, Austria, July 1991.
• 12: T. Eiter and G. Gottlob. Propositional Circumscription and Extended Closed World Reasoning are Hf-complete. Technical Report CD/TR 91- 20, Christian Doppler Laboratory for Expert Systems, Vienna University of Technology, Austria, May 1991. To appear in Theorelical Computer Science.
• 13: T. Eiter and G. Gottlob. Higher Level Complexity Results for Abduction. Technical report, Information Systems Dept., TU Vienna, 1992. forthcoming.
• 14: R. Fagin, G. Kuper, J. Ullman, and M. Y. Vardi. Updating Logical Databases. In P. Kanellakis and F. Preparata, editors, Advances #n Computing Research, volume 3. JAI Press, 1986.
• 15: 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]
• 16: K. D. Forbus. Introducing Actions into Qualitative Simulation. In Proceedings IJCAI-89, pages 1273- 1278, 1989.
• 17: P. Ggrdenfors. Knowledge in Flux. Bradford Books, MIT Press, 1988.
• 18: 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
• 19: Michael Gelfond , H. Przymusinska , Teodor C. Przymusinski, On the relationship between circumscription and negation as failure, Artificial Intelligence, v.38 n.1, p.75-94, Feb. 1989 [doi>10.1016/0004-3702(89)90068-4]
• 20: M Gelfond , H Przymusinska, Negation as failure: Careful closure procedure, Artificial Intelligence, v.30 n.3, p.273-288, Dec. 1986 [doi>10.1016/0004-3702(86)90001-9]
• 21: 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]
• 22: Matthew L. Ginsberg, A circumscriptive theorem prover, Artificial Intelligence, v.39 n.2, p.209-230, June 1989 [doi>10.1016/0004-3702(89)90026-X]
• 23: G. Gottlob. Complexity Results for Nonmonotonic Logics. Technical Report CD/TR 91-24, Christian Doppler Laboratory for Expert Systems, Vienna University of Technology, Austria, August 1991. To appear in Journal of Logic and Computation.
• 24: G. Grahne. Updates and Counterfactuals. In Proceedings KR-91, pages 269-276, 1991.
• 25: G. Grahne and A. O. Mendelzon. Updates and Subjunctive Queries. Technical Report KRR- TR-91-4, University of Toronto, CS Dept., July 1991. Also Proceedings Workshop on Nonstandard Queries and Answers, Toulouse, July 1-3, 1991, pp. 33-52.
• 26: J. Hartmanis, New developments in structural complexity theory, Theoretical Computer Science, v.71 n.1, p.79-93, 13 March 1990 [doi>10.1016/0304-3975(90)90191-J]
• 27: David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 28: J. Kadin. pNP{O(logn)} and Sparse Turing- Complete Sets for NP. Journal of Computer and System Sczences, 39:282-298, 1989.
• 29: H. Katsuno and A. O. Mendelzon. On the Difference between Updating a Knowledge Base and Revising it. In Proceedings KR-91, pages 387 - 395, 1991.
• 30: Hirofumi Katsuno , Alberto O. Mendelzon, Propositional knowledge base revision and minimal change, Artificial Intelligence, v.52 n.3, p.263-294, Dec. 1991 [doi>10.1016/0004-3702(91)90069-V]
• 31: A. Keller and M. Winslett-Wilkinson. On the Use of an Extended Relational Model to Handle Changing Incomplete Information. IEEE Transactions on Software Engineering, SE:11(7):620-633, 1985.
• 32: 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]
• 33: D. Lewis. Counterfactuals. Harvard University Press, Cambridge, MA, 1973.
• 34: Vladimir Lifschitz, Closed-world databases and circumscription, Artificial Intelligence, v.27 n.2, p.229-235, Nov. 1985 [doi>10.1016/0004-3702(85)90055-4]
• 35: W. Marek and M. Truszczyfisky. Modal logic for default reasoning. Annals of Mathemal#cs and Artificial Intelligence, 1:275-302, 1990.
• 36: J. McCarthy. Circumscription- A Form of Non-Monotonic Reasoning. Artificial Intelligence, 13:27-39, 1980.
• 37: 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]
• 38: D. McDermott and J. Doyle. Non-Monotonic Logic I. Artific,al Intelligence, 13:41-72, 1980.
• 39: Jack Minker, On Indefinite Databases and the Closed World Assumption, Proceedings of the 6th Conference on Automated Deduction, p.292-308, June 07-09, 1982
• 40: 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]
• 41: Bernhard Nebel, A knowledge level analysis of belief revision, Proceedings of the first international conference on Principles of knowledge representation and reasoning, p.301-311, December 1989
• 42: B. Nebel. Belief Revision and Default Reasoning: Syntax-Based Approaches. In PTvceedings KR-91, pages 417-428, 1991.
• 43: C. H. Papadimitriou and M. Yannakakis. The Complexity of Facets (And Some Facets of Complexity). Journal of Computer and System Sczences, 28:244-259, 1984.
• 44: Teodor C. Przymusinski, An algorithm to compute circumscription, Artificial Intelligence, v.38 n.1, p.49-73, Feb. 1989 [doi>10.1016/0004-3702(89)90067-2]
• 45: R. Reiter. On Closed-World Databases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 55-76. Plenum Press, New York, 1978.
• 46: R. Reiter. A Logic for Default Reasoning. A rtzficzal Intelligence, 13:81-132, 1980.
• 47: 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]
• 48: 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
• 49: K. Satoh. Nonmonotonic Reasoning by Minimal Belief Revision. In Proceedings of the Internalional Conference on Fifth Generatzon Compuler Systems, pages 455-462, 1988.
• 50: A. Weber. Updating Propositional Formulas. In Proceedings of the First Conference on Ez'pe#'t Database Systems, pages 487-500, 1986.
• 51: M. Winslett. Reasoning about Action Using a Possible Models Approach. In Proceedzngs AAAI- 88, pages 89-93, 1988.
• 52: Marianne Winslett, Updating logical databases, Cambridge University Press, New York, NY, 1991
• 53: M. Winslett. Circumscriptive Semantics for Updating Databases. Annals of Mathematics aTzd Artificial intelligence, 3:429-450, 1991.
• 54: A. Yahya and L. Henschen. Deduction in Non- Horn Databases. Journal of Automated Reasoning, 1(2):141-160, 1985.
• 55: Aidong Zhang , Wiktor Marek, On the classification and existence of structures in default logic, Fundamenta Informaticae, v.13 n.4, p.485-499, Dec. 1990

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  H. Information Systems
  H.2 DATABASE MANAGEMENT

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Nonmonotonic reasoning and belief revision

General Terms:
Algorithms, Languages, Theory