On the Complexity of Fragments of Modal Logics
Linh Anh Nguyen · 2004
Abstract. We study and give a summary of the complexity of 15 basic normal modal logics under the restriction to the Horn fragment and/or bounded modal depth. As new results, we show that the satisfiability problem of sets of Horn modal clauses with modal depth bounded by k ≥ 2 in the modal logics K 4 and KD4 is PSPACE-complete, in K is NP-complete. We also show that the satisfiability problem of modal formulas with modal depth bounded by 1 in K 4, KD4, and S4 is NPcomplete; the satisfiability problem of sets of Horn modal clauses with modal depth bounded by 1 in K, K 4, KD4, and S4 is PTIME-complete. 1