I am writing a paper in which I want to include complexity results for different modal logics and possibly add a reference to a specific paper.

At the moment I have the following:

K- no restrictions on the frame, NPComplete

T- reflexive, NPComplete

K4- transitive, PSpaceComplete

S4 and S4.3 also PSpaceComplete

S5- symmetric, transitive and reflexive, NPComplete.

I am not able to find any results regarding complexity of the following axioms for modal logic:

D- serial

KB- symmetric

B- reflexive, symmetric

The above 3 modal logics are important for me and I really need the complexity results with a specific paper. If anyone could help me out here it would be great thanks.


1 Answer 1


You might find interesting some of the results in On the Complexity of Fragments of Modal Logics by Linh Anh Nguyen (in Advances in Modal Logic, 2004: 249-268). A version of the paper is available in the home page of Nyugen.

And probably you are already familiar with A guide to completeness and complexity of modal logics by Joseph Y. Halpern and Yoram Moses (in Artificial Intelligence 54, 1992, pp. 319-379). A version of the paper similar to the published version is available in postscript and pdf in the home page of Halpern.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.