How many variables does one need to prove PSpace-hardness of modal logics
Alexander Chagrov, Михаил Николаевич Рыбаков · 2002
this paper is to nd out the minimal number of variables one needs to prove PSPACE-hardness of the decision problem for standard modal logics. Since this problem (even in the full in nite language) is in PSPACE, we thereby shall get PSPACE-completeness of the corresponding nite-variable (or even variable-free) fragments. For some of the logics considered |T, S4, Grz, GL| these fragments contain a sole variable, while variable-free fragments of these logics are decidable by polynomial algorithms. On the other hand, K and K4 do have very expressive PSPACE-hard variable-free fragments