Complexity Transfer for Modal Logic (Extended Abstract)
Edith Hemaspaandra · Logic in Computer Science · 1994
In this paper, we prove general theorems about the relationship between the complexity of multi-modal logics and the complexity of their una-modal fragments. Halpern and Moses [HM85] show that the complexity of a multi-modal logic without any interaction between the modalities may be higher than the complexity of the individual fragments. In this paper, we show that under reasonable assumptions the complexity can increase only if the complexity of all the uni-modal fragments is below PSPACE. In addition, we completely characterize what happens if the complexity of all fragments is below PSPACE.