Riccardo Rosati.
In Proceedings of the Fourth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'97), Lecture Notes in Artificial Intelligence, volume 1265, pages 76-91, Springer, 1997.
We study the computational properties of the propositional fragment of Levesque's logic of only knowing. In particular, we show that the problem of reasoning with only knowing in the propositional case lies at the second level of the polynomial hierarchy. Thus, it is as hard as reasoning in the majority of propositional formalisms for nonmonotonic reasoning, like default logic, circumscription and autoepistemic logic, and it is easier than reasoning in propositional formalisms based on the minimal knowledge paradigm, which is strictly related to the notion of only knowing.
@String{LPNMR-97 = "Proceedings of the Fourth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'97)"}
@String{SV = "Springer"}
@String{LNAI = "Lecture Notes in Artificial Intelligence"}
@Inproceedings{Rosa97b,
author = "Riccardo Rosati",
title = "Complexity of Only Knowing: {T}he Propositional Case",
booktitle = LPNMR-97,
pages = "76--91",
publisher = SV,
series = LNAI,
volume = 1265,
year = 1997,
}