01299nas a2200145 4500008004100000245006200041210006200103260004100165300001000206520083000216100002001046700001901066700001901085856004901104 2009 eng d00aLogical Omniscience as a Computational Complexity Problem0 aLogical Omniscience as a Computational Complexity Problem aStanford University, CaliforniabACM a14-233 aThe 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$}.1 aArtemov, Sergei1 aKuznets, Roman1 aHeifetz, Aviad uhttp://www.iam.unibe.ch/ltgpub/2009/ak09.pdf