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)
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$}.