complexity of modal logic axioms

Question

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.

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.