Paper: On the complexity of epistemic reasoning (at LICS 1989)

Authors: Moshe Y. Vardi

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 = 	 {Moshe Y. Vardi},
    title = 	 {On the complexity of epistemic reasoning},
    booktitle =  {Proceedings of the Fourth Annual IEEE Symposium on Logic in Computer Science (LICS 1989)},
    year =	 {1989},
    month =	 {June}, 
    pages =      {243--252},
    location =   {Pacific Grove, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }