2026-07-25T01:58:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1356 2024-03-06T10:33:00Z ddc:004 open_access

On the Complexity of Elementary Modal Logics Hemaspaandra, Edith Schnoor, Henning 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Edith Hemaspaandra and Henning Schnoor 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1356 urn:nbn:de:0030-drops-13561 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1356 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode