The price of universality (Q1815426)

The paper is an involved contribution to the area of complexity of satisfiability problems for propositional modal logics. It explores the effect of adding the global modalities, the `universal' modality (\(U\)-modality) and the `reachability' modality (\(R\)-modality), on the mentioned complexity. Firstly, the author shows an example of a uni-modal logic with decidable (in NP, in fact) satisfiability problem where adding the \(U\)-modality causes undecidability and the \(R\)-modality causes high undecidability. The logic can be even supposed to be finitely axiomatizable and canonical; thus a conjecture by Goranko and Passy is refuted. Then the intuitive conjecture that the \(R\)-modality is `at least as hard' as the \(U\)-modality is confirmed -- for well-behaved classes of frames; for non-well-behaved classes it is demonstrated that the \(U\)-modality can be arbitrarily harder than the \(R\)-modality. In the end, it is shown why EXPTIME-hardness appears when the \(U\)-modality or the \(R\)-modality are added to a multi-modal logic with independent modalities. The special classes where this is not true are fully characterized.