Conservative Extensions in Modal Logic

Every normal modal logic L gives rise to the consequence relation \phi |=L \psi which holds if, and only if, \psi is true in a world of an L-model whenever \phi is true in that world. We consider the following algorithmic problem for L. Given two modal formulas \phi_1 and \phi_2, decide whether \phi_1\wedge \psi_2 is a conservative extension of \phi_1 in the sense that whenever \phi_1 \wedge \phi_2 |=L \psi and \psi does not contain propositional variables not occurring in \phi_1, then \phi_1 |=L \psi. We first prove that the conservativeness problem is coNExpTime-hard for all modal logics of unbounded width (which have rooted frames with more than N successors of the root, for any N < \omega). Then we show that this problem is (i) coNExpTime-complete for S5 and K, (ii) in ExpSpace for S4 and (iii) ExpSpace-complete for GL.3 (the logic of finite strict linear orders). The proofs for S5 and K use the fact that these logics have uniform interpolants of exponential size.