Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2306-2310.
Abstract
There has been a great deal of work on characterizing the complexity of the satisfiability and validity problem for modal logics. In particular, Ladner showed that the satisfiability problem for all logics between K and S4 is PSPACE-hard, while for S5, it is NP-complete. We show that it is negative introspection axiom that causes the gap: if we add this axiom to any modal logic between K and S4, then the satisfiability problem becomes NP-complete. Indeed, the satisfiability problem is NP-complete for any modal logic that includes the negative introspection axiom.
@inproceedings{ijcai2007p371,
title = {Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic},
author = {Halpern, Joseph Y. and Rêgo, Leandro Chaves},
booktitle = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {2306--2310},
year = {2007},
url = {https://ijcai.org/proceedings/2007/371},
}
TY - CPAPER TI - Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic AU - Halpern, Joseph Y. AU - Rêgo, Leandro Chaves T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 2306 EP - 2310 UR - https://ijcai.org/proceedings/2007/371 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
