%0 Conference Paper
%B Theoretical Aspects of Rationality and Knowledge, Proceedings of the Twelfth Conference (TARKĀ 2009)
%D 2009
%T Logical Omniscience as a Computational Complexity Problem
%A Sergei Artemov
%A Roman Kuznets
%E Aviad Heifetz
%X 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 \emph{not logically omniscient} if for any valid knowledge assertion~$\mathcal{A}$ of type \emph{$F$~is known}, a proof of~$F$ in~$E$ can be found in polynomial time in the size of~$\mathcal{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 \emph{$t$~is a justification for~$F$}.
%B Theoretical Aspects of Rationality and Knowledge, Proceedings of the Twelfth Conference (TARKĀ 2009)
%I ACM
%C Stanford University, California
%P 14-23
%G eng
%U http://www.iam.unibe.ch/ltgpub/2009/ak09.pdf
%R 10.1145/1562814.1562821