Logical omniscience as a computational complexity problem

ABSTRACT

The logical omniscience feature assumes that an epistemic agent knows all logical consequences of her assumptions. This paper offers a general theoretical framework that views logical omniscience as a computational complexity problem. We suggest the following approach: we assume that the knowledge of an agent is represented by an epistemic logical system E; we call such an agent not logically omniscient if for any valid knowledge assertion A of type F is known, a proof of F in E can be found in polynomial time in the size of A. We show that agents represented by major modal logics of knowledge and belief are logically omniscient, whereas agents represented by justification logic systems are not logically omniscient with respect to t is a justification for F.

REFERENCES

• 1: Natasha Alechina , Brian Logan, Ascribing beliefs to resource bounded agents, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, July 15-19, 2002, Bologna, Italy [doi>10.1145/544862.544948]
• 2: Sergei {N.} Artemov and Roman Kuznets. Logical omniscience via proof complexity. In Zoltán Ésik, editor, Computer Science Logic, 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL. Szeged, Hungary, September 25--29, 2006, Proceedings, volume 4207 of Lecture Notes in Computer Science, pages 135--149. Springer, 2006.
• 3: Sergei Artemov , Elena Nogina, Introducing Justification into Epistemic Logic, Journal of Logic and Computation, v.15 n.6, p.1059-1073, December 2005 [doi>10.1093/logcom/exi053]
• 4: Sergei N. Artemov. Operational modal logic. Technical Report MSI 95--29, Cornell University, December 1995.
• 5: Sergei N. Artemov. Explicit provability and constructive semantics. Bulletin of Symbolic Logic, 7(1):1--36, March 2001.
• 6: Sergei {N.} Artemov. The logic of justification. The Review of Symbolic Logic, 1(4):477--513, December 2008.
• 7: R Aumann, Reasoning about knowledge in economics, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.251-251, March 1986, Monterey, California, United States
• 8: Vladimir N. Brezhnev. On explicit counterparts of modal logics. Technical Report CFIS 2000--05, Cornell University, 2000.
• 9: Samuel R. Buss , Roman Kuznets, The NP-Completeness of Reflected Fragments of Justification Logics, Proceedings of the 2009 International Symposium on Logical Foundations of Computer Science, p.122-136, January 03-03, 2009, Deerfield Beach, FL [doi>10.1007/978-3-540-92687-0_9]
• 10: Stephen Cook , Robert Reckhow, On the lengths of proofs in the propositional calculus (Preliminary Version), Proceedings of the sixth annual ACM symposium on Theory of computing, p.135-148, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803893]
• 11: Jennifer J. Elgot-Drapkin, Michael Miller, and Donald Perlis. Memory, reason, and time: The step-logic approach. In Robert Cummins and John Pollock, editors, Philosophy and AI, Essays at the Interface, chapter 4, pages 79--104. MIT Press, 1991.
• 12: R. Fagin , J. Y. Halpern, Belief, awareness, and limited reasoning, Artificial Intelligence, v.34 n.1, p.39-76, Dec. 1987 [doi>10.1016/0004-3702(87)90003-8]
• 13: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi, A nonstandard approach to the logical omniscience problem, Artificial Intelligence, v.79 n.2, p.203-240, Dec. 1995 [doi>10.1016/0004-3702(94)00060-3]
• 14: Joseph Y. Halpern , Yoram Moses, A guide to completeness and complexity for modal logics of knowledge and belief, Artificial Intelligence, v.54 n.3, p.319-379, April 1992 [doi>10.1016/0004-3702(92)90049-4]
• 15: Joseph Y. Halpern , Riccardo Pucella, Dealing with logical omniscience, Proceedings of the 11th conference on Theoretical aspects of rationality and knowledge, June 25-27, 2007, Brussels, Belgium [doi>10.1145/1324249.1324273]
• 16: Jaakko Hintikka. Knowledge and Belief: An Introduction to the Logic of the Two Notions. Cornell University Press, 1962.
• 17: Jaakko Hintikka. Impossible possible worlds vindicated. Journal of Philosophical Logic, 4(3):475--484, August 1975.
• 18: Kurt Konolige, A Deduction Model of Belief, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1986
• 19: Nikolai V. Krupski, On the complexity of the reflected logic of proofs, Theoretical Computer Science, v.357 n.1, p.136-142, 25 July 2006 [doi>10.1016/j.tcs.2006.03.015]
• 20: Roman Kuznets. On decidability of the logic of proofs with arbitrary constant specifications. In 2004 Annual Meeting of the Association for Symbolic Logic, Carnegie Mellon University, Pittsburgh, PA, May 19--23, 2004, volume 11(1) of Bulletin of Symbolic Logic, page 111. Association for Symbolic Logic, March 2005. Abstract.
• 21: Roman Kuznets , Sergei Artemov, Complexity issues in justification logic, City University of New York, New York, NY, 2008
• 22: Hector J. Levesque. A logic of implicit and explicit belief. In Ronald J. Brachman, editor, Proceedings of the Fourth National Conference on Artificial Intelligence, AAAI 1984, Austin, Texas, August 6--10, 1984, pages 198--202. AAAI Press, 1984.
• 23: Richard Montague. Universal grammar. Theoria, 36:373--398, 1970.
• 24: R Moore, Reasoning about knowledge in artificial intelligence, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.81-81, March 1986, Monterey, California, United States
• 25: Yoram Moses, Resource-bounded Knowledge, Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, p.261-275, March 01, 1988
• 26: Eric Pacuit. A note on some explicit modal logics. In Proceedings of the 5th Panhellenic Logic Symposium, pages 117--125, Athens, Greece, July 25--28, 2005. University of Athens.
• 27: R. Parikh, Knowledge and the problem of logical omniscience, Proceedings of the Second International Symposium on Methodologies for intelligent systems, p.432-439, December 1987, Charlotte, North Carolina, United States
• 28: Rohit Parikh, Logical Omniscience, Selected Papers from the International Workshop on Logical and Computational Complexity, p.22-29, October 13-16, 1994
• 29: Rohit Parikh, Logical omniscience and common knowledge: WHAT do we know and what do WE know?, Proceedings of the 10th conference on Theoretical aspects of rationality and knowledge, June 10-12, 2005, Singapore
• 30: Rohit Parikh. Sentences, belief and logical omniscience, or what does deduction tell us? The Review of Symbolic Logic, 1(4):459--476, December 2008.
• 31: Pavel Pudlák. The lengths of proofs. In Samuel R. Buss, editor, Handbook of Proof Theory, volume 137 of Studies in Logic and the Foundations of Mathematics, chapter VIII, pages 547--637. Elsevier, 1998.
• 32: Veikko Rantala. Impossible worlds semantics and logical omniscience. Acta Philosophica Fennica, 35:106--115, 1982.
• 33: Natalia Rubtsova. Evidence reconstruction of epistemic modal logic S5. In Dima Grigoriev, John Harrison, and Edward A. Hirsch, editors, Computer Science -- Theory and Applications, First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8--12, 2006, Proceedings, volume 3967 of Lecture Notes in Computer Science, pages 313--321. Springer, 2006.
• 34: Dana Scott. Advice in modal logic. In K. Lambert, editor, Philosophical Problems in Logic, pages 143--173. Reidel, 1970.
• 35: Hyun Song Shin and Timothy Williamson. Representing the knowledge of Turing machines. Theory and Decision, 37(1):125--146, July 1994.
• 36: M Vardi, On epistemic logic and logical omniscience, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.293-305, March 1986, Monterey, California, United States
• 37: Heinrich Wansing. A general possible worlds framework for reasoning about knowledge and belief. Studia Logica, 49(4):523--539, December 1990.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Proof theory; Computational logic

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

General Terms:
Algorithms, Design, Theory