Paper: On the complexity of epistemic reasoning (at LICS 1989)
Authors: Vardi, M.Y.Abstract
A study is made of the complexity of the decision problem for epistemic logics based on R. Montague's (1968) and R. Scott's (1970) semantics. The interest is in finding out how assumptions about the agents' reasoning power affect the complexity of reasoning about the agents' knowledge. A spectrum of assumptions is studied, and it is shown that the complexity of the logic under different assumptions is always in NP or PSPACE. The mental faculty that raises the complexity of the logic from NP to PSPACE is pinpointed. It is the ability to combine distinct items of knowledge
BibTeX
@InProceedings{Vardi-Onthecomplexityofep,
author = {Vardi, M.Y.},
title = {On the complexity of epistemic reasoning},
booktitle = {Proceedings of the Fourth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1989},
year = 1989,
editor = {Rohit Parikh},
month = {June},
pages = {243--252},
location = {Pacific Grove, CA, USA},
publisher = {IEEE Computer Society Press}
}