@conference {1349,
title = {Logical Omniscience as a Computational Complexity Problem},
booktitle = {Theoretical Aspects of Rationality and Knowledge, Proceedings of the Twelfth Conference (TARK~2009)},
year = {2009},
pages = {14-23},
publisher = {ACM},
organization = {ACM},
address = {Stanford University, California},
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 \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$}.},
doi = {10.1145/1562814.1562821},
url = {http://www.iam.unibe.ch/ltgpub/2009/ak09.pdf},
author = {Sergei Artemov and Roman Kuznets},
editor = {Aviad Heifetz}
}