Tenyo Takahashi

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

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...