Algorithmical properties of quasinormal modal logics with linear finite model property

We investigate the relationship between the complexity of a propositional modal logic and the complexity of models refuting the formulas not belonging to the logic. It is well-known that for many normal monomodal propositional logics the same constructions are used to establish both the PSPACE-completeness of a logic and the exponential lower-bound for the number of worlds in Kripke models refuting formulas not belonging to the logic. The same holds true for superintuitionistic propositional logics. As far as we know, there are no known mathematical criteria capturing this connection. In this paper, we show that if we discard the normality condition, and thus consider non-normal modal logics, we can construct quasi-normal logics with a linear model property whose complexity problem can be arbitrarily high. Moreover, this holds true if we only consider variable-free fragments of such logics.