  Modal logics are widely used in computer science. The complexity of modal
satisfiability problems has been investigated since the 1970s, usually proving
results on a case-by-case basis. We prove a very general classification for a
wide class of relevant logics: Many important subclasses of modal logics can be
obtained by restricting the allowed models with first-order Horn formulas. We
show that the satisfiability problem for each of these logics is either
NP-complete or PSPACE-hard, and exhibit a simple classification criterion.
Further, we prove matching PSPACE upper bounds for many of the PSPACE-hard
logics.
