Elementary modal logics and circuit complexity

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 the circuit complexity class uniform ${\mathsf{AC}}^0$. As an application, we construct infinitely many finitely axiomatizable $K4$-stable logics that are not elementary. This result provides a negative answer to Problem 6.4 in [Bezhanishvili et al., 2018] for $K4$-stable logics.

arXiv comment15 pages, 3 figures