On the complexity of epistemic reasoning

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 affects 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.