TY - CONF
T1 - Logical Omniscience as a Computational Complexity Problem
T2 - Theoretical Aspects of Rationality and Knowledge, Proceedings of the Twelfth Conference (TARKĀ 2009)
Y1 - 2009
A1 - Sergei Artemov
A1 - Roman Kuznets
ED - Aviad Heifetz
AB - 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$}.
JF - Theoretical Aspects of Rationality and Knowledge, Proceedings of the Twelfth Conference (TARKĀ 2009)
PB - ACM
CY - Stanford University, California
UR - http://www.iam.unibe.ch/ltgpub/2009/ak09.pdf
ER -