On the Complexity of Prefix Formulas in Modal Logic of Subset Spaces
Most logics used in Computer Science have an intractable satisfiability (model-checking, derivability) problem. This restricts their general applicability severely. Only confining to smaller classes of admissible formulas can probably bring down the complexity bounds. In the present paper we follow this strategy for the subset space logic recently proposed by Moss and PARIKH [MP, DMP]. Forming nSAT as in sentential logic, but with prefix formulas instead of literals, we obtain nice generalizations of the following results well-known from the propositional case: nSAT ϵ P if n ≤ 2, and nSAT is NP-complete if n 2 ≥ 3.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten