Logical Omniscience as a Computational Complexity Problem

TitleLogical Omniscience as a Computational Complexity Problem
Publication TypeConference Paper
Year of Publication2009
AuthorsArtemov, S, Kuznets, R
EditorHeifetz, A
Conference NameTheoretical Aspects of Rationality and Knowledge, Proceedings of the Twelfth Conference (TARK 2009)
Pagination14-23
PublisherACM
Conference LocationStanford University, California
AbstractThe 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$}.
URLhttp://www.iam.unibe.ch/ltgpub/2009/ak09.pdf
DOI10.1145/1562814.1562821