Non-elementary modal logics, assuming P $\neq$ NP

Abstract

A modal logic is elementary if it is sound and complete with respect to an elementary class of Kripke frames. We prove that if a finitely axiomatizable modal logic L is elementary, then the validity problem for L, which asks whether a given finite Kripke frame validates L, is in P. This allows us to transfer complexity results in graph theory to the study of elementarity of modal logics. As an application, we construct infinitely many finitely axiomatizable K4-stable logics that are not elementary, assuming P $\neq$ NP. This result provides a conditional negative answer to an open question in [Bezhanishvili et al., 2018] for K4-stable logics.