About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
LICS 1989
Conference paper
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.